A.Oh Those Palindromes

直接排序之后輸出就行了。

證明的話直接跟據(jù)同一種字符最多能在多少個(gè)回文串中貢獻(xiàn)答案就行了。

#include <bits/stdc++.h> #define for1(a,b,i) for(int i=a;i<=b;++i) #define FOR2(a,b,i) for(int i=a;i>=b;--i) using namespace std; typedef long long ll; #define M 500005 int n; char s[M]; int cnt[M];int main () {//freopen("a.in","r",stdin);scanf("%d%s",&n,s+1);for1(1,n,i) ++cnt[s[i]-'a'];for1(0,25,i) for1(1,cnt[i],j) putchar('a'+i);puts(""); } View Code

B.Labyrinth

顯然如果向左走的多，向右走一定多，直接最短路就行了。

#include <bits/stdc++.h> #define for1(a,b,i) for(int i=a;i<=b;++i) #define FOR2(a,b,i) for(int i=a;i>=b;--i) using namespace std; typedef long long ll; #define M 2005 int n,m; char s[M]; bool vis[M][M]; int ax,ay,x_,y_,a[M][M]; int f[4]={0,0,1,-1},g[4]={1,-1,0,0};struct node {int x,y;}dis[M][M];int main () { // freopen("a.in","r",stdin);scanf("%d%d%d%d%d%d",&n,&m,&ax,&ay,&x_,&y_);for1(1,n,i) {scanf("%s",s+1);for1(1,m,j) a[i][j]=s[j]=='.';}queue <node> q;q.push((node){ax,ay});for1(1,n,i) for1(1,m,j) dis[i][j].x=2e9,dis[i][j].y=2e9;dis[ax][ay]=(node){0,0};while (!q.empty()) {node t=q.front();q.pop();vis[t.x][t.y]=0;FOR2(3,0,i) {int tox=t.x+f[i];int toy=t.y+g[i];if(!tox||!toy||tox>n||toy>m||!a[tox][toy]) continue;if(dis[tox][toy].x<=dis[t.x][t.y].x+(i==1)) continue;dis[tox][toy]=dis[t.x][t.y];if(i==0) ++dis[tox][toy].y;if(i==1) ++dis[tox][toy].x;if(!vis[tox][toy]) vis[tox][toy]=1,q.push((node){tox,toy});}}int cnt=0;for1(1,n,i) for1(1,m,j) if(a[i][j]) {cnt+=dis[i][j].x<=x_&&dis[i][j].y<=y_;}cout<<cnt<<endl; } View Code

C.Dwarves,Hats and Extrasensory Abilities?

直接找個(gè)軸二分點(diǎn)就行了。

注意最后輸出直線的時(shí)候就不能過這個(gè)軸上的整點(diǎn)了，會(huì)重。

#include <bits/stdc++.h> #define for1(a,b,i) for(int i=a;i<=b;++i) #define FOR2(a,b,i) for(int i=a;i>=b;--i) using namespace std; typedef long long ll; inline int read() {int f=1,sum=0;char x=getchar();for(;(x<'0'||x>'9');x=getchar()) if(x=='-') f=-1;for(;x>='0'&&x<='9';x=getchar()) sum=sum*10+x-'0';return f*sum; }#define M 1000005 int n; char s[10];int main () {//freopen("a.in","r",stdin);cin>>n;cout<<"1 0"<<endl;cin>>(s+1);int co=s[1];int l=0,r=1e9,mid;for1(2,n,i) {mid=l+r>>1;cout<<1<<" "<<mid<<endl;cin>>(s+1);if(s[1]==co) l=mid;else r=mid;}mid=l+r>>1;cout<<0<<" "<<l<<" "<<2<<" "<<r<<endl; } /* 30 0 1 1 0 1 1 0 0 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1 1 0 1 1 1 */ View Code

D.Candies for Children

沒想到可以按照$sqrt(n)$分類。

就是吃兩個(gè)的個(gè)數(shù)和吃的輪數(shù)是相互限制的。

所以就分這個(gè)討論就好了，最后一個(gè)人可以吃不完直接++s然后強(qiáng)制最后一個(gè)人吃兩個(gè)就行了。

#include <bits/stdc++.h> #define min(a,b) ((a)<(b)?(a):(b)) #define max(a,b) ((a)>(b)?(a):(b)) #define for1(a,b,i) for(int i=a;i<=b;++i) #define FOR2(a,b,i) for(int i=a;i>=b;--i) using namespace std; typedef long long ll;ll n,k,x,y;int main () { // freopen("a.in","r",stdin);cin>>n>>x>>y>>k;x=y-x+1+(y<x?n:0);y=n-x;if(x>k) return puts("-1"),0;if(k/n>n) {if(!y) swap(x,y);int ans=-1;for1(0,n,i) {int s=k%(n+i);if(s>=x&&s<=2*x&&i-s+x>=0&&i-s+x<=y) ans=i;}++k;for1(ans+1,n,i) {int s=k%(n+i);if(s>x&&s<=2*x&&i-s+x>=0&&i-s+x<=y) ans=i;}printf("%d\n",ans);}else {ll ans=-1;if(k<=2*x) ans=min(k-x+1,x)+y;FOR2((k-x)/n,1,i) {ll c=k-x-n*i;ll a=c,b=-c,t;t=(c-1)/(i+1)+1;a-=i*t,b+=(i+1)*t;if(a<0||b>y) continue;t=min((y-b)/(i+1),a/i);a-=i*t,b+=(i+1)*t;if(a<=x) ans=a+b;}++k;FOR2((k-x)/n,1,i) {ll c=k-x-n*i;ll a=c,b=-c,t;t=(c-1)/(i+1)+1;a-=i*t,b+=(i+1)*t;if(a<=0||b>y) continue;t=min((y-b)/(i+1),(a-1)/i);a-=i*t,b+=(i+1)*t;//這里取max啊-_-if(a<=x) ans=max(ans,a+b);}printf("%lld\n",ans);} } View Code

F.String Journey

需要分析很多性質(zhì)。

我只想到了$O(n^{3/2})$的。

1>：長(zhǎng)度一定是$K,K-1......1$。

2>：對(duì)于一個(gè)端點(diǎn)$l$若$[l,l+len-1]$成立，則$\forall i\leq len$都成立。

3>：$f[i] \leq f[i+1]+1$。

性質(zhì)還是很容易證明的，然后就可以用后綴數(shù)組搞了。

#include <bits/stdc++.h> #define min(a,b) ((a)<(b)?(a):(b)) #define max(a,b) ((a)>(b)?(a):(b)) #define for1(a,b,i) for(int i=a;i<=b;++i) #define FOR2(a,b,i) for(int i=a;i>=b;--i) using namespace std; typedef long long ll; inline int read () {int f=1,sum=0;char x=getchar();for(;(x<'0'||x>'9');x=getchar()) if(x=='-') f=-1;for(;x>='0'&&x<='9';x=getchar()) sum=sum*10+x-'0';return f*sum; }#define M 1000005 int n; char s[M]; int Max[M*4]; int las,node_num; int Lg[M],RMQ[M][20]; int g[M],h[M],sa[M],rank_[M]; int f[M],fa[M],mx[M],pos[M],nxt[M][26]; vector <pair<int,int> > to[M];inline void dfs(int x,int &cnt) {int size=to[x].size();if(pos[x]) {++cnt;sa[cnt]=pos[x];rank_[pos[x]]=cnt;}sort(to[x].begin(),to[x].end());for1(1,size,i) {pair <int,int> v=to[x][i-1];dfs(v.second,cnt);} }inline void build() {int t=0;las=node_num=1;FOR2(n,1,i) {int c=s[i]-'a';int p=las,np=las=++node_num;mx[np]=mx[p]+1;while (p&&!nxt[p][c]) nxt[p][c]=np,p=fa[p];if(!p) fa[np]=1;else {int q=nxt[p][c];if(mx[q]==mx[p]+1) fa[np]=q;else {int nq=++node_num;mx[nq]=mx[p]+1;memcpy(nxt[nq],nxt[q],sizeof(nxt[q]));fa[nq]=fa[q],fa[q]=fa[np]=nq;while (nxt[p][c]==q) nxt[p][c]=nq,p=fa[p];}}f[las]=pos[las]=i;}for1(1,node_num,i) ++h[mx[i]];for1(1,node_num,i) h[i]+=h[i-1];for1(1,node_num,i) rank_[h[mx[i]]--]=i;FOR2(node_num,1,i) f[fa[rank_[i]]]=f[rank_[i]];for1(2,node_num,i) to[fa[i]].push_back(make_pair(s[f[i]+mx[fa[i]]],i));dfs(1,t);t=0;for(int i=1;i<=n;h[rank_[i++]]=t,t-=t!=0) for(;s[i+t]==s[sa[rank_[i]-1]+t];++t);for1(2,n,i) Lg[i]=Lg[i>>1]+1;FOR2(n,1,i) {RMQ[i][0]=h[i];for1(1,19,j) RMQ[i][j]=min(RMQ[i][j-1],RMQ[i+(1<<j-1)][j-1]);} }inline int get_min(int l,int r) {int t=Lg[r-l+1];return min(RMQ[l][t],RMQ[r-(1<<t)+1][t]); }inline void T_add(int g,int l,int r,int x,int y) {if(l==r) return Max[g]=y,void();int mid=l+r>>1;if(x<=mid) T_add(g<<1,l,mid,x,y);else T_add(g<<1|1,mid+1,r,x,y);Max[g]=max(Max[g<<1],Max[g<<1|1]); }inline int query_l(int g,int l,int r,int x,int y) {if(x<l||Max[g]<y) return 0;if(l==r) return l;int mid=l+r>>1;int ans=query_l(g<<1|1,mid+1,r,x,y);if(ans) return ans;else return query_l(g<<1,l,mid,x,y); }inline int query_r(int g,int l,int r,int x,int y) {if(x>r||Max[g]<y) return 0;if(l==r) return l;int mid=l+r>>1;int ans=query_r(g<<1,l,mid,x,y);if(ans) return ans;else return query_r(g<<1|1,mid+1,r,x,y); }inline bool check(int x,int len) {--len;int t=query_l(1,1,n,rank_[x]-1,len);if(t&&get_min(t+1,rank_[x])>=len) return 1;t=query_r(1,1,n,rank_[x]+1,len);if(t&&get_min(rank_[x]+1,t)>=len) return 1;t=query_l(1,1,n,rank_[x+1]-1,len);if(t&&get_min(t+1,rank_[x+1])>=len) return 1;t=query_r(1,1,n,rank_[x+1]+1,len);return t&&get_min(rank_[x+1]+1,t)>=len; }int main () {//freopen("a.in","r",stdin);scanf("%d%s",&n,s+1);build();g[n]=1;for(int i=n,now=n+1;i>=1;--i) {while (g[i]>1) {while (now>i+g[i]) --now,T_add(1,1,n,rank_[now],g[now]);if(check(i,g[i])) break;--g[i];}g[i-1]=g[i]+1;}for1(2,n,i) g[i]=max(g[i],g[i-1]);printf("%d\n",g[n]); } View Code

轉(zhuǎn)載于:https://www.cnblogs.com/asd123www/p/9851254.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #516 (Div. 1) 题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。