「CF360X」Codeforces Round #210 (Div. 1)
A. Levko and Array Recovery
求出每个位置初始值的最大值，然后check一下
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 100000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; int a[5005],b[5005]; int f[5005],l[5005],r[5005],v[5005]; int main() { n=read();m=read(); for(int i=1;i<=n;i++)a[i]=inf; for(int i=1;i<=m;i++) { f[i]=read();l[i]=read();r[i]=read();v[i]=read(); } for(int k=1;k<=m;k++) { if(f[k]==1) for(int i=l[k];i<=r[k];i++) b[i]+=v[k]; else for(int i=l[k];i<=r[k];i++) a[i]=min(a[i],v[k]-b[i]); } for(int i=1;i<=n;i++)b[i]=a[i]; for(int k=1;k<=m;k++) { if(f[k]==1) for(int i=l[k];i<=r[k];i++) b[i]+=v[k]; else { int mx=-inf; for(int i=l[k];i<=r[k];i++) mx=max(mx,b[i]); if(mx!=v[k]){puts("NO");return 0;} } } puts("YES"); for(int i=1;i<=n;i++)printf("%d ",a[i]); return 0; } |
B. Levko and Array
二分答案，f(i)表示前i个的最小修改次数，且i不修改，枚举上一个不修改的位置转移
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,K; int a[2005],f[2005]; bool check(ll x) { for(int i=1;i<=n;i++) { f[i]=i-1; for(int j=1;j<i;j++) if(abs(a[i]-a[j])<=(i-j)*x) f[i]=min(f[i],f[j]+(i-j-1)); if(f[i]+n-i<=K)return 1; } return 0; } int main() { n=read();K=read(); for(int i=1;i<=n;i++)a[i]=read(); ll l=0,r=2*inf; while(l<=r) { int mid=(l+r)>>1; if(check(mid))r=mid-1; else l=mid+1; } printf("%d\n",(int)l); return 0; } |
C. Levko and Strings
f(i,j)表示前i个字母，beauty值为j的合法方案，\(t_k=s_k\)(k>j)
1.在第i位放一个比s[i]大的字母，枚举上一个位置i-k-1满足\(s_{i-k-1}!=t_{i-k-1}\)
产生的新的beauty子串(k+1)*(n-i+1)
2.在第i位放一个比s[i]小的字母，不产生新的beauty子串
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; ll f[2005][2005],sum[2005]; char s[2005]; int main() { n=read();m=read(); scanf("%s",s+1); f[0][0]=1;sum[0]++; for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) { f[i][j]=sum[j]*(s[i]-'a')%mod; for(int k=0;k<i&&(k+1)*(n-i+1)<=j;k++) f[i][j]=(f[i][j]+f[i-k-1][j-(k+1)*(n-i+1)]*('z'-s[i]))%mod; sum[j]=(sum[j]+f[i][j])%mod; } ll ans=0; for(int i=0;i<=n;i++) ans=(ans+f[i][m])%mod; printf("%d\n",(int)ans); return 0; } |
D. Levko and Sets
我数学很差QAQ 看英文题解吧。。。
似乎就是裴蜀定理+gcd乱搞一下
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,p,tot,ans; int a[100005],b[100005],q[100005]; int d[100005],f[100005]; ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } int qpow(ll a,int b) { ll ans=1; for(int i=b;i;i>>=1,a=a*a%p) if(i&1)ans=ans*a%p; return ans; } int main() { n=read();m=read();p=read(); for(int i=1;i<=n;i++)a[i]=read(); int t=p-1; for(int i=1;i<=m;i++)b[i]=read(); for(int i=1;i<=n;i++)t=gcd(t,b[i]); for(int i=1;i*i<=p-1;i++) if((p-1)%i==0) { d[++tot]=i; if(i*i!=p-1)d[++tot]=(p-1)/i; } sort(d+1,d+tot+1); for(int i=1;i<=n;i++) { a[i]=qpow(a[i],t); for(int j=1;j<=tot;j++) if(qpow(a[i],d[j])==1) { q[i]=(p-1)/d[j];break; } } sort(q+1,q+n+1); n=unique(q+1,q+n+1)-q-1; for(int i=n;i;i--) { f[i]=(p-1)/q[i]; for(int j=i+1;j<=n;j++) if(q[j]%q[i]==0)f[i]-=f[j]; ans+=f[i]; } printf("%d\n",ans); return 0; } |
E. Levko and Game
先把所有边长定为r
如果s1->x的距离<s2->x的距离，则从x出发的边长定为l，即让两人都走这条边会使第一个人更合算
先判断能不能赢，再判断能不能平局
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1e16 #define mod 1000000007 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int s1,s2,T; int n,m,K,cnt; struct edge{ int from,to,next,l,r; }e[20005]; int last[10005],q[10005]; ll da[10005],db[10005]; bool vis[10005]; void insert(int u,int v,int l,int r) { e[++cnt]=(edge){u,v,last[u],l,r};last[u]=cnt; } void spfa(ll *dis,int s) { for(int i=1;i<=n;i++)dis[i]=inf,vis[i]=0; int head=0,tail=1; q[0]=s;dis[s]=0;vis[s]=1; while(head!=tail) { int x=q[head];head++;vis[x]=0; if(head==10000)head=0; for(int i=last[x];i;i=e[i].next) if(dis[x]+e[i].r<dis[e[i].to]) { dis[e[i].to]=dis[x]+e[i].r; if(!vis[e[i].to]) { q[tail++]=e[i].to; if(tail==10000)tail=0; } vis[e[i].to]=1; } } } bool solve(int f) { bool flag=1; while(flag) { flag=0; spfa(da,s1);spfa(db,s2); for(int i=m+1;i<=m+K;i++) if(da[e[i].from]<db[e[i].from]+f&&e[i].l!=e[i].r) { e[i].r=e[i].l; flag=1; } if(da[T]<db[T]+f) { if(f)puts("DRAW"); else puts("WIN"); for(int i=m+1;i<=m+K;i++) printf("%d ",e[i].r); return 1; } } return 0; } int main() { n=read();m=read();K=read(); s1=read();s2=read();T=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(),w=read(); insert(u,v,w,w); } for(int i=1;i<=K;i++) { int u=read(),v=read(),l=read(),r=read(); insert(u,v,l,r); } if(!solve(0)) if(!solve(1)) puts("LOSE"); return 0; } |
计数器 9854562
OI 课件=>
OI 课件=>
黄学长我仰慕您！