Codeforces Round #376 (Div. 2)

T1:

　　题意：给你一个环，从‘a'-->'b'--->'c'--->....--->'z'---'a'

　　　　　然后开始于’a'，给你一串字符，求从‘a'开始一直依次走字符要走多少步

　　题解：模拟

T2:

　　题意：给你n个数字，你可以给这个数字-2（无数个）或者自己-1，自己后面一个数-1，问是否能全部为0；

　　题解：模拟

T3:　　

　　题意：给你一些袜子，每个袜子有自己的颜色，然后给你很多对（x-y)希望将（x-y）染成同一种颜色，求最小染色步数

　　题解：并查集+线段树

T4:

　　题意：给你一些字符串，然后给你一种移动规则：移动一步，每个字符%m+1；求最小移动步数使得字符串大小按字典序排序

　　题解：将一些不和法区间弄出来用线段树或者差分维护即可

T5:　　

　　题意：两个人轮流按某个规则取数（从左向右取数字可以取【2--n】个，获得权值为数字和，同时取完后在最左边加一个权值为数字和的数

　　　　　希望先手-后手的差最大[两个人绝顶聪明]

　　题解：设一个dp[i]表示从i--n中开始先手先取的最大差值

　　　　　dp[i]=max(sum[j]-dp[j]) i+1<=j<=n　

　　　　　于是考虑从后往前做可将时间优化为O[n]的　

　　题意：给你一些数字，你可以选择其中一个不动的数字X，其他数字可以删减使得所有数为X的倍数,求所有数字之和的最大值！

　　题解：考虑一个数一定在X*(j-1)和X*(j)之中，因为不能+所以一定会变为X*(j-1)所以我只需要知道X*(J-1)--X*j中有多少个数字存在原数列中

　　　　　时间复杂度为n*log（maxn) 可能重复出现某个数字，于是我们用vis记录一下即可！

代码集合：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
char s[105];
int n;
int read()
{
    int x=0,f=1; char ch;
    while (ch=getchar(),ch<'0'||ch>'9') if (ch=='-') f=-1;
    while (x=x*10+ch-'0',ch=getchar(),ch>='0'&&ch<='9');
    return x*f;
}
int main()
{
    scanf("%s",s+1); n=strlen(s+1);
    char p='a'; int ans=0;
    for (int i=1; i<=n; i++)
    {
        ans+=min(abs(s[i]-p),26-abs(p-s[i])); p=s[i];
    }
    cout<<ans<<endl;
    return 0;
}

#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cstdio> using namespace std; int n; int a[200005]; int read() { int x=0,f=1; char ch; while (ch=getchar(),ch<'0'||ch>'9') if (ch=='-') f=-1; while (x=x*10+ch-'0',ch=getchar(),ch>='0'&&ch<='9'); return x*f; } int main() { n=read(); bool bo=true; for (int i=1; i<=n; i++) { a[i]=read()-a[i-1]; if (a[i]<0) {bo=false; break;} a[i]=(a[i]-a[i]/2*2); if (a[i]==0) continue; if (i==n) {bo=false;} } if (bo) cout<<"YES"<<endl; else cout<<"NO"<<endl; return 0; }

#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cstdio> #include<vector> #define N 210005 using namespace std; int n,m,k; int fa[N],a[N],b[N],col[N],tot,ans=0; int sum[N*6]; vector<int>rec[N]; int read() { int x=0,f=1; char ch; while (ch=getchar(),ch<'0'||ch>'9') if (ch=='-') f=-1; while (x=x*10+ch-'0',ch=getchar(),ch>='0'&&ch<='9'); return x*f; } int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]); } void clear(int k,int l,int r) { if (l==r){sum[k]=0; return;} int mid=(l+r)>>1; if (sum[k*2]!=0) clear(k*2,l,mid); if (sum[k*2+1]!=0) clear(k*2+1,mid+1,r); sum[k]=0; } void change(int k,int l,int r,int x) { if (l==r){sum[k]++; return ;} int mid=(l+r)>>1; if (x<=mid) change(k*2,l,mid,x); else change(k*2+1,mid+1,r,x); sum[k]=max(sum[k*2],sum[k*2+1]); } int main() { n=read(); m=read(); k=read(); for (int i=1; i<=n; i++) col[i]=read(); for (int i=1; i<=n; i++) fa[i]=i; for (int i=1; i<=m; i++) { int x=read(),y=read(); int fx=find(x),fy=find(y); if (fx!=fy) fa[fx]=fy; } for (int i=1; i<=n; i++) fa[i]=find(i); for (int i=1; i<=n; i++) { rec[fa[i]].push_back(i); if (fa[i]==i) tot++,b[tot]=fa[i]; } for (int i=1; i<=tot; i++) { int x=b[i]; clear(1,1,k); for (int j=0; j<rec[x].size(); j++) { change(1,1,k,col[rec[x][j]]); } int tmp=sum[1]; ans+=rec[x].size()-tmp; } printf("%d ",ans); return 0; }

#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cstdio> #include<vector> #define N 1000010 using namespace std; int n,m,sum[N],a[N]; vector<int>rev[N]; int read() { int x=0,f=1; char ch; while (ch=getchar(),ch<'0'||ch>'9') if (ch=='-') f=-1; while (x=x*10+ch-'0',ch=getchar(),ch>='0'&&ch<='9'); return x*f; } void ins(int l,int r){sum[l]++;sum[r+1]--;} void solve(int k) { int tot=min(a[k],a[k+1]); for (int i=0; i<tot; i++) { int x=rev[k][i],y=rev[k+1][i]; if (x!=y) { if (x<y) ins(m-y+1,m-x); else ins(0,m-x),ins(m-y+1,m-1); return ; } } if (a[k]>a[k+1]) {cout<<-1<<endl; exit(0);} } int main() { n=read(); m=read(); for (int i=1; i<=n; i++) { a[i]=read(); for (int j=1; j<=a[i]; j++) rev[i].push_back(read()); } for (int i=1; i<n; i++) solve(i); int tmp=0; for (int i=0; i<m; i++) { tmp+=sum[i]; if (!tmp) {printf("%d ",i); return 0;} } printf("-1 "); return 0; }

#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cstdio> #define N 200005 using namespace std; int n; int a[N],sum[N],f[N]; int read() { int x=0,f=1; char ch; while (ch=getchar(),ch<'0'||ch>'9') if (ch=='-') f=-1; while (x=x*10+ch-'0',ch=getchar(),ch>='0'&&ch<='9'); return x*f; } int main() { n=read(); for (int i=1; i<=n; i++) sum[i]=sum[i-1]+read(); int fuckls=sum[n]; for (int i=n-1; i>=1; i--) { f[i]=fuckls; fuckls=max(fuckls,sum[i]-f[i]); } cout<<f[1]<<endl; }

#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cstdio> #define ll long long #define N 200005 using namespace std; bool vis[N]; int a[N],n; ll ans; int read() { int x=0,f=1; char ch; while (ch=getchar(),ch<'0'||ch>'9') if (ch=='-') f=-1; while (x=x*10+ch-'0',ch=getchar(),ch>='0'&&ch<='9'); return x*f; } int main() { n=read(); for (int i=1; i<=n; i++) a[i]=read(); sort(a+1,a+n+1); for (int i=1; i<=n; i++) { ll maxn=0; if (vis[a[i]]) continue; vis[a[i]]=1; for (int j=a[i]; j<=a[n]; j+=a[i]) { int tmp=a[i]+j; int l=lower_bound(a+1,a+n+1,j)-a; int r=lower_bound(a+1,a+n+1,tmp)-a; maxn+=1ll*(r-l)*j; } ans=max(ans,maxn); } printf("%I64d ",ans); return 0; }

Codeforces Round #376 (Div. 2)

相关推荐