A: 签到.
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- #define ll long long
- char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
- int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
- int read()
- {
- int x=0,f=1;char c=getchar();
- while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
- while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
- return x*f;
- }
- int main()
- {
- int n=read(),m=read();
- if (m*2-1<=n) cout<<"YES";else cout<<"NO";
- return 0;
- }
B: 直接按欧拉路判, 才不管只有四个点.
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- #define ll long long
- char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
- int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
- int read()
- {
- int x=0,f=1;char c=getchar();
- while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
- while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
- return x*f;
- }
- int a[5],fa[5];
- int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
- int main()
- {
- for (int i=1;i<=4;i++) fa[i]=i;
- for (int i=1;i<=3;i++)
- {
- int x=read(),y=read();
- a[x]++,a[y]++;fa[find(x)]=find(y);
- }
- for (int i=1;i<=4;i++)
- if (find(i)!=find(1)) {cout<<"NO";return 0;}
- int cnt=0;
- for (int i=1;i<=4;i++)
- {
- if (a[i]&1) cnt++;
- }
- if (cnt==2) cout<<"YES";
- else {cout<<"NO";return 0;}
- return 0;
- }
C: 相当于可以用 1 代价获得 1 收益, 用 2 代价获得 b-a 收益. 瞎讨论即可. 注意 2 代价获得 b-a 收益的前提是当前有至少 a 块饼干.
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- #define ll long long
- char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
- int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
- int read()
- {
- int x=0,f=1;char c=getchar();
- while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
- while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
- return x*f;
- }
- int main()
- {
- int n=read(),a=read(),b=read();
- b-=a;
- if (b<=2) cout<<n+1;
- else
- {
- if (n<a) cout<<n+1;
- else
- {
- n-=a-1;
- ll ans=a;
- ans+=1ll*b*(n/2);
- if (n&1) ans++;
- cout<<ans;
- }
- }
- return 0;
- }
D: 相当于找一个形如 0 非零偶数 奇数 非零偶数 0 的序列 (每一段长度任意且可以为空), 使该序列与原序列差的绝对值之和最小. 赛时智商急剧下降搞了一大堆前缀和, 最后屯完题交的时候网又卡了, 发现 wa 掉的时候只剩下 5min, 于是就没救了. 实际上直接 dp 不能再好写, 即 f[i][0/1/2/3/4] 表示第 i 个位置在第 j 段中时的最小和.
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- #define ll long long
- #define N 200010
- char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
- int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
- int read()
- {
- int x=0,f=1;char c=getchar();
- while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
- while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
- return x*f;
- }
- int n,a[N],delta[N];
- ll f[N][5];
- //ll ans,f[N][2],s[N],g[N][2],h[N];
- int main()
- {
- n=read();
- for (int i=1;i<=n;i++) a[i]=read();
- /*for (int i=1;i<=n;i++)
- if (a[i]==0) delta[i]=2;
- else delta[i]=a[i]&1;
- for (int i=1;i<=n;i++) g[i][0]=g[i-1][0]+delta[i],s[i]=s[i-1]+a[i];
- ll u=0;
- for (int i=1;i<=n;i++)
- {
- u=min(u,s[i]-g[i][0]);
- f[i][0]=g[i][0]+u;
- }
- for (int i=n;i>=1;i--) g[i][1]=g[i+1][1]+delta[i],s[i]=s[i+1]+a[i];
- u=0;
- for (int i=n;i>=1;i--)
- {
- u=min(u,s[i]-g[i][1]);
- f[i][1]=g[i][1]+u;
- }
- for (int i=1;i<=n;i++) ans+=a[i];
- u=0;
- for (int i=1;i<=n;i++) ans=min(ans,f[i][1]+s[i-1]);
- for (int i=1;i<=n;i++) h[i]=h[i-1]+(a[i]&1^1);
- for (int i=1;i<=n+1;i++)
- {
- ans=min(ans,f[i][1]+u+h[i-1]);
- u=min(u,f[i][0]-h[i]);
- }*/
- for (int i=1;i<=n;i++)
- {
- f[i][0]=f[i-1][0];
- for (int j=1;j<=4;j++)
- f[i][j]=min(f[i][j-1],f[i-1][j]);
- f[i][0]+=a[i],f[i][4]+=a[i];
- f[i][1]+=a[i]==0?2:(a[i]&1);
- f[i][3]+=a[i]==0?2:(a[i]&1);
- f[i][2]+=a[i]&1^1;
- }
- ll ans=f[n][0];for (int i=1;i<=4;i++) ans=min(ans,f[n][i]);
- cout<<ans;
- return 0;
- }
F: 大胆猜想序列合法当且仅当序列前 i 个位置的红球个数<= 前 i 个人的红球个数, 序列前 i 个位置的蓝球个数<= 前 i 个人的蓝球个数, 然后就是个思博 dp 了.
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- #define ll long long
- #define N 2010
- #define P 998244353
- char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
- int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
- int read()
- {
- int x=0,f=1;char c=getchar();
- while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
- while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
- return x*f;
- }
- int n,a[N],u,v,s[N][2],f[N<<1][N<<1];
- char S[N];
- void inc(int &x,int y){x+=y;if (x>=P) x-=P;}
- int main()
- {
- scanf("%s",S+1);
- n=strlen(S+1);
- for (int i=1;i<=n;i++) a[i]=S[i]-'0';
- for (int i=1;i<=n;i++) u+=2-a[i],v+=a[i];
- for (int i=1;i<=n;i++) s[i][0]=s[i-1][0]+2-a[i],s[i][1]=s[i-1][1]+a[i];
- f[0][0]=1;
- for (int i=0;i<=u;i++)
- for (int j=0;j<=v;j++)
- if (i|j)
- {
- if (s[min(n,i+j)][0]>=i&&s[min(n,i+j)][1]>=j)
- {
- if (i) inc(f[i][j],f[i-1][j]);
- if (j) inc(f[i][j],f[i][j-1]);
- }
- }
- cout<<f[u][v];
- return 0;
- }
result:rank 207 rating +38 莫名其妙上黄了但非常不爽啊.
来源: http://www.bubuko.com/infodetail-2948937.html