A. Eating Soup
time limit per test1 second memory limit per test256 megabytes
The three friends, Kuro, Shiro, and Katie, met up again! It's time for a party...
What the cats do when they unite? Right, they have a party. Since they wanted to have as much fun as possible, they invited all their friends. Now nn cats are at the party, sitting in a circle and eating soup. The rules are simple: anyone having finished their soup leaves the circle.
Katie suddenly notices that whenever a cat leaves, the place where she was sitting becomes an empty space, which means the circle is divided into smaller continuous groups of cats sitting next to each other. At the moment Katie observes, there are mm cats who left the circle. This raises a question for Katie: what is the maximum possible number of groups the circle is divided into at the moment?
Could you help her with this curiosity?
You can see the examples and their descriptions with pictures in the "Note" section.Input
The only line contains two integers nn and mm (2≤n≤10002≤n≤1000, 0≤m≤n0≤m≤n) — the initial number of cats at the party and the number of cats who left the circle at the moment Katie observes, respectively.Output
Print a single integer — the maximum number of groups of cats at the moment Katie observes.
Examplesinput
7 4
output
3
input
6 2
output
2
input
3 0
output
1
input
2 2
output
0
Note
In the first example, originally there are 77 cats sitting as shown below, creating a single group:
At the observed moment, 44 cats have left the table. Suppose the cats 22, 33, 55 and 77 have left, then there are 33 groups remaining. It is possible to show that it is the maximum possible number of groups remaining.
In the second example, there are 66 cats sitting as shown below:
At the observed moment, 22 cats have left the table. Suppose the cats numbered 33 and 66 left, then there will be 22 groups remaining ({1,2}{1,2}and {4,5}{4,5}). It is impossible to have more than 22 groups of cats remaining.
In the third example, no cats have left, so there is 11 group consisting of all cats.
In the fourth example, all cats have left the circle, so there are 00 groups.
签到题
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
const int maxn=(int)2e5+100;
int n,m;
int main(){
cin>>n>>m; if(m==0){return puts("1"),0;}
if(m>n/2) m=n-m;
printf("%d\n",m);
}
B2. Cat Party (Hard Edition)
time limit per test1 second memory limit per test256 megabytes
This problem is same as the previous one, but has larger constraints.
Shiro's just moved to the new house. She wants to invite all friends of her to the house so they can play monopoly. However, her house is too small, so she can only invite one friend at a time.
For each of the nn days since the day Shiro moved to the new house, there will be exactly one cat coming to the Shiro's house. The cat coming in the ii-th day has a ribbon with color uiui. Shiro wants to know the largest number xx, such that if we consider the streak of the first xx days, it is possible to remove exactly one day from this streak so that every ribbon color that has appeared among the remaining x−1x−1will have the same number of occurrences.
For example, consider the following sequence of uiui: [2,2,1,1,5,4,4,5][2,2,1,1,5,4,4,5]. Then x=7x=7 makes a streak, since if we remove the leftmost ui=5ui=5, each ribbon color will appear exactly twice in the prefix of x−1x−1 days. Note that x=8x=8 doesn't form a streak, since you must remove exactly one day.
Since Shiro is just a cat, she is not very good at counting and needs your help finding the longest streak.Input
The first line contains a single integer nn (1≤n≤1051≤n≤105) — the total number of days.
The second line contains nn integers u1,u2,…,unu1,u2,…,un (1≤ui≤1051≤ui≤105) — the colors of the ribbons the cats wear.Output
Print a single integer xx — the largest possible streak of days.
Examplesinput
13 1 1 1 2 2 2 3 3 3 4 4 4 5
output
13
input
5 10 100 20 200 1
output
5
input
1 100000
output
1
input
7 3 2 1 1 4 5 1
output
6
input
6 1 1 1 2 2 2
output
5
Note
In the first example, we can choose the longest streak of 1313 days, since upon removing the last day out of the streak, all of the remaining colors 11, 22, 33, and 44 will have the same number of occurrences of 33. Note that the streak can also be 1010 days (by removing the 1010-th day from this streak) but we are interested in the longest streak.
In the fourth example, if we take the streak of the first 66 days, we can remove the third day from this streak then all of the remaining colors 11, 22, 33, 44 and 55 will occur exactly once.
简单题，多加几个特判
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
const int maxn=(int)1e5+100;
int ans,n,num[maxn],has[maxn],max_time;
set<int> s;
int main(){
cin>>n;
rep(i,1,n){
int x;scanf("%d",&x); s.insert(x);
has[num[x]]--;num[x]++;has[num[x]]++;
max_time=max(max_time,num[x]);
if(num[x]==1){
if(max_time==1&&has[max_time]==(int)s.size())
ans=i;
if(max_time!=1&&has[max_time]==(int)s.size()-1)
ans=i;
}
if(num[x]==max_time){
if(has[max_time]==(int)s.size()-1&&has[1]==1)
ans=i;
if(has[max_time]==1&&has[max_time-1]==(int)s.size()-1)
ans=i;
}
if(has[max_time]==1&&has[max_time-1]==(int)s.size()-1){
ans=i;
}
}
printf("%d\n",ans);
}
C2. Power Transmission (Hard Edition)
time limit per test3 seconds memory limit per test256 megabytes
This problem is same as the previous one, but has larger constraints.
It was a Sunday morning when the three friends Selena, Shiro and Katie decided to have a trip to the nearby power station (do not try this at home). After arriving at the power station, the cats got impressed with a large power transmission system consisting of many chimneys, electric poles, and wires. Since they are cats, they found those things gigantic.
At the entrance of the station, there is a map describing the complicated wiring system. Selena is the best at math among three friends. He decided to draw the map on the Cartesian plane. Each pole is now a point at some coordinates (xi,yi)(xi,yi). Since every pole is different, all of the points representing these poles are distinct. Also, every two poles are connected with each other by wires. A wire is a straight line on the plane infinite in both directions. If there are more than two poles lying on the same line, they are connected by a single common wire.
Selena thinks, that whenever two different electric wires intersect, they may interfere with each other and cause damage. So he wonders, how many pairs are intersecting? Could you help him with this problem?Input
The first line contains a single integer nn (2≤n≤10002≤n≤1000) — the number of electric poles.
Each of the following nn lines contains two integers xixi, yiyi (−104≤xi,yi≤104−104≤xi,yi≤104) — the coordinates of the poles.
It is guaranteed that all of these nn points are distinct.Output
Print a single integer — the number of pairs of wires that are intersecting.
Examplesinput
4 0 0 1 1 0 3 1 2
output
14
input
4 0 0 0 2 0 4 2 0
output
6
input
3 -1 -1 1 0 3 1
output
0
Note
In the first example:
In the second example:
Note that the three poles (0,0)(0,0), (0,2)(0,2) and (0,4)(0,4) are connected by a single wire.
In the third example:
答案就是不重合的直线数的组合数减去每一组平行直线的组合数；
也即，假设一组平行直线的条数是t条，那么答案就要减去t*(t-1)/2;
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pll pair<int,int>
typedef long long ll;
const int maxn=(int)2e5+100;
int gcd(int x,int y){
if(!y) return x;
return gcd(y,x%y);
}
map<pll,set<int>> mp;
set<pll> s;
int n;
struct node{
int x,y;
}p[1010];
int main(){
cin>>n;
rep(i,1,n) scanf("%d%d",&p[i].x,&p[i].y);
rep(i,1,n) rep(j,i+1,n){
int xx=p[i].x-p[j].x,yy=p[i].y-p[j].y;
if(xx<0) xx=-xx,yy=-yy;
int g=gcd(xx,yy); xx/=g;yy/=g;
int cc=p[i].y*xx-p[i].x*yy;
mp[{-yy,xx}].insert(cc);
s.insert({-yy,xx});
}
ll tot=0,sub=0;
for(auto i=s.begin();i!=s.end();++i){
ll sz=mp[*i].size();
tot+=sz;
sub+=sz*(sz-1)/2;
}
printf("%lld\n",tot*(tot-1)/2-sub);
}
D. Mysterious Code
time limit per test2 seconds memory limit per test256 megabytes
During a normal walk in the forest, Katie has stumbled upon a mysterious code! However, the mysterious code had some characters unreadable. She has written down this code as a string ?c consisting of lowercase English characters and asterisks ("*"), where each of the asterisks denotes an unreadable character. Excited with her discovery, Katie has decided to recover the unreadable characters by replacing each asterisk with arbitrary lowercase English letter (different asterisks might be replaced with different letters).
Katie has a favorite string ?s and a not-so-favorite string ?t and she would love to recover the mysterious code so that it has as many occurrences of ?s as possible and as little occurrences of ?t as possible. Formally, let's denote ?(?,?)f(x,y) as the number of occurrences of ?y in ?x (for example, ?(??????,??)=2f(aababa,ab)=2). Katie wants to recover the code ?′c′ conforming to the original ?c, such that ?(?′,?)−?(?′,?)f(c′,s)−f(c′,t) is largest possible. However, Katie is not very good at recovering codes in general, so she would like you to help her out.Input
The first line contains string ?c (1≤|?|≤10001≤|c|≤1000) — the mysterious code . It is guaranteed that ?c consists of lowercase English characters and asterisks "*" only.
The second and third line contain strings ?s and ?t respectively (1≤|?|,|?|≤501≤|s|,|t|≤50, ?≠?s≠t). It is guaranteed that ?s and ?t consist of lowercase English characters only.Output
Print a single integer — the largest possible value of ?(?′,?)−?(?′,?)f(c′,s)−f(c′,t) of the recovered code.
Examplesinput
***** katie shiro
output
1
input
caat caat a
output
-1
input
*a* bba b
output
0
input
*** cc z
output
2
Note
In the first example, for ?′c′ equal to "katie" ?(?′,?)=1f(c′,s)=1 and ?(?′,?)=0f(c′,t)=0, which makes ?(?′,?)−?(?′,?)=1f(c′,s)−f(c′,t)=1 which is the largest possible.
In the second example, the only ?′c′ conforming to the given ?c is "caat". The corresponding ?(?′,?)−?(?′,?)=1−2=−1f(c′,s)−f(c′,t)=1−2=−1.
In the third example, there are multiple ways to recover the code such that ?(?′,?)−?(?′,?)f(c′,s)−f(c′,t) is largest possible, for example "aaa", "aac", or even "zaz". The value of ?(?′,?)−?(?′,?)=0f(c′,s)−f(c′,t)=0 for all of these recovered codes.
In the fourth example, the optimal recovered code ?′c′ would be "ccc". The corresponding ?(?′,?)−?(?′,?)=2f(c′,s)−f(c′,t)=2.
看到有通配符的主串和多个模式串匹配，第一想法肯定AC自动机要上的
容易想到在s串的最后记的是1，t串最后记的是-1
接下来在getFail时需要加上cntword[now]+=cntword[fail[now]]，即当选到当前节点 now 时候，加上可能匹配到的一个完整的 s 或者一个完整的 t 的影响。假设 s = "cbaaaa" , t = "aa" ,当 j 节点在 s 下的第一个 ‘a' 时， fail[ j ] 在 t 的第一个 ‘a’ , cntword[ j ] 不进行修改，当 j 节点在 s 下的第二个 'a' 时， fail[ j ] 在 t 的第二个 ‘a' , cntword[ j ] 更新值为 cntword[ j ]-1 ,表示在匹配过程中到 s 的 "baa" 时，恰好也匹配到了一个 t ，我们需要减去一个完整的 t 带来答案的影响，同理，到 s 的第三个 ‘a’ 不修改， s 的第四个 'a' 修改为 cntword[ j ]-1
接下来用dp[i][j]表示主串中第i位到Trie树中第j个节点的最大答案，那么状态转移方程就是dp[i+1][now]=max(dp[i+1][now],dp[i][j]+cntword[now])
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
const int maxn=(int)2e5+100;
const int INF=0x7f7f7f7f;
string a,b,c;
int trie[1010][26];
int cntword[maxn],dp[1010][1010];
int fail[maxn];
int cnt = 0;
void insert(string s,int v){
int root = 0;
for(int i=0;i<s.size();i++){
int next = s[i] - 'a';
if(!trie[root][next])
trie[root][next] = ++cnt;
root=trie[root][next];
}
cntword[root]+=v;
}
void getFail(){
queue<int> q;
for(int i=0;i<26;i++){
if(trie[0][i]){
fail[trie[0][i]] = 0;
q.push(trie[0][i]);
}
}
while(!q.empty()){
int now=q.front();q.pop();
for(int i=0;i<26;i++){
if(trie[now][i]){
fail[trie[now][i]] = trie[fail[now]][i];
q.push(trie[now][i]);
}
else trie[now][i] = trie[fail[now]][i];
}
cntword[now]+=cntword[fail[now]];
}
}
int main(){
cin>>a>>b>>c;
insert(b,1); insert(c,-1); getFail();
memset(dp,-INF,sizeof(dp)); dp[0][0]=0;
int len=a.length();
rep(i,0,len-1) rep(j,0,cnt) rep(k,0,25)
if(a[i]=='*'||a[i]=='a'+k){
int now=trie[j][k];
dp[i+1][now]=max(dp[i+1][now],dp[i][j]+cntword[now]);
}
int ans=-INF;
rep(i,0,cnt) ans=max(ans,dp[len][i]);
printf("%d\n",ans);
}
