Educational Codeforces Round 8"/>
Educational Codeforces Round 8
开始填坑_(:з」∠)_
628A - Tennis Tournament 20171124
小学数学题,\((x,y)=((n-1)\cdot(2b+1),np)\)
#include<stdlib.h> #include<stdio.h> #include<math.h> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,b,p,x,y; int main() {scanf("%d%d%d",&n,&b,&p);x=(n-1)*(2*b+1),y=n*p;printf("%d %d\n",x,y);return 0; }View Code
628B - New Skateboard 20171124
由于能根据末尾的两个数字判断出是否为4的倍数,直接每相邻两位判断一下就好了
#include<stdlib.h> #include<stdio.h> #include<math.h> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define LL long long string s; LL ans; bool check(int k){return k%4==0;} int main() {cin>>s;ans=check(s[0]-'0');for(LL i=1;i<s.size();i++)ans+=check(s[i]-'0'),ans+=i*check(s[i-1]*10+s[i]);printf("%I64d\n",ans);return 0; }View Code
628C - New Skateboard 20171124
让每一位修改产生的距离尽可能大即可
#include<stdlib.h> #include<stdio.h> #include<math.h> #include<cstring> #include<iostream> #include<algorithm> using namespace std; string s; int n,k,f[100001]; int main() {scanf("%d%d",&n,&k);cin>>s;for(int i=1;i<=n;i++)f[i]=max(s[i-1]-'a','z'-s[i-1])+f[i-1];if(f[n]<k)return printf("-1\n"),0;for(int i=0;i<n;i++){if(k>=f[i+1]-f[i])s[i]=(s[i]-'a'>'z'-s[i])?'a':'z';else s[i]=(s[i]-k>='a')?s[i]-k:s[i]+k;k-=f[i+1]-f[i];if(k<=0)break;}cout<<s<<endl;return 0; }View Code
628D - Magic Numbers 20190301
比较恶心的DP,首先将区间\((l,r)\)的询问转化为两次对区间\((1,n)\)的询问
令\(f[i][j][k]\)表示当前进行到第\(i\)位,除以\(m\)的余数为\(j\)时,与\(n\)的大小关系为\(k\)的方案数
循环时\(i\)从\(1\)到\(n\),通过枚举第\(i\)位的数字来推出\(j\)进行转移
接下去就是各种细节处理了
#include<bits/stdc++.h> using namespace std; #define N 2005 #define LL long long #define MOD 1000000007 LL m,d,f[N][N][3],ans; char s[N]; LL rua() {LL n=strlen(s+1);memset(f,0,sizeof(f));for(LL j=1;j<=9;j++)if(j!=d){if(j<s[1]-'0')f[1][j%m][0]++;if(j==s[1]-'0')f[1][j%m][1]++;if(j>s[1]-'0')f[1][j%m][2]++;}for(LL i=1;i<n;i++)for(LL j=0;j<m;j++)for(LL k=0;k<3;k++)if(f[i][j][k]){//cout<<i<<" "<<j<<" "<<k<<" "<<f[i][j][k]<<endl;if(i&1){if(k==0)(f[i+1][(j*10ll+d)%m][k]+=f[i][j][k])%=MOD;if(k==1){if(d<s[i+1]-'0')(f[i+1][(j*10ll+d)%m][0]+=f[i][j][k])%=MOD;else if(d==s[i+1]-'0')(f[i+1][(j*10ll+d)%m][1]+=f[i][j][k])%=MOD;else if(d>s[i+1]-'0')(f[i+1][(j*10ll+d)%m][2]+=f[i][j][k])%=MOD;}if(k==2)(f[i+1][(j*10ll+d)%m][k]+=f[i][j][k])%=MOD;continue;}for(LL l=0;l<=9;l++)if(l!=d){if(k==0)(f[i+1][(j*10ll+l)%m][k]+=f[i][j][k])%=MOD;if(k==1){if(l<s[i+1]-'0')(f[i+1][(j*10ll+l)%m][0]+=f[i][j][k])%=MOD;else if(l==s[i+1]-'0')(f[i+1][(j*10ll+l)%m][1]+=f[i][j][k])%=MOD;else if(l>s[i+1]-'0')(f[i+1][(j*10ll+l)%m][2]+=f[i][j][k])%=MOD;}if(k==2)(f[i+1][(j*10ll+l)%m][k]+=f[i][j][k])%=MOD;}}LL res=0;//for(LL j=0;j<m;j++)for(LL k=0;k<2;k++)if(f[n][j][k])cout<<n<<" "<<j<<" "<<k<<" "<<f[n][j][k]<<endl;for(LL i=1;i<n;i++)for(LL k=0;k<3;k++)(res+=f[i][0][k])%=MOD;(res+=f[n][0][0]+f[n][0][1])%=MOD;return res; } bool check() {LL n=strlen(s+1);for(LL i=1;i<=n;i++){if((i&1) && s[i]==d+'0')return false;if(i%2==0 && s[i]!=d+'0')return false;}LL r=0;for(LL i=1;i<=n;i++)r=(r*10+s[i]-'0')%m;return r==0; } int main() {scanf("%I64d%I64d",&m,&d);scanf("%s",s+1);ans=MOD-rua()+check();//cout<<rua()<<endl;scanf("%s",s+1);ans+=rua();//cout<<rua()<<endl;return printf("%I64d\n",ans%MOD),0; }View Code
628E - Zbazi in Zeydabad 20190305
这题只能说。。。bitset大法好,莽就完事了
#include<bits/stdc++.h> using namespace std; #define N 3005 #define LL long long LL n,m,ans; bitset<N>a[N],b[N],c[N]; int get() {char ch=getchar();while(ch!='.' && ch!='z')ch=getchar();return ch=='z'; } int main() {scanf("%I64d%I64d",&n,&m);for(LL i=0;i<n;i++)for(LL j=0;j<m;j++)a[i][m-j-1]=get(),b[i].set(),c[i].set();for(LL i=0;i<min(m,n);i++){for(LL j=0;j<n;j++)b[j]&=a[j]>>i;for(LL j=0;j<n-i;j++)c[j]&=a[j+i]>>i,ans+=(b[j]&b[j+i]&c[j]).count();}return printf("%I64d\n",ans),0; }View Code
628F - Bear and Fair Set 20190306
标解是网络流,但是有种瞎搞的方法不知道为什么能过_(:з」∠)_
考虑\(\{0,1,2,3,4\}\)的所有子集\(A\),对每个区间,计算出满足\(i\%5\epsilon A\)的\(i\)的个数,并与该区间可取数字的个数取\(min\),加起来后若个数小于\(\frac{|A|\cdot n}{5}\),则一定无解
若考虑完所有子集后依旧没有出现不合法的情况,则一定有解(本弱不会证,求大佬证明)
#include<bits/stdc++.h> using namespace std; #define mp make_pair int nn,n,b,q; vector<pair<int,int> >d; int main() {d.push_back(mp(0,0));scanf("%d%d%d",&n,&b,&q),nn=n;d.push_back(mp(b,n));for(int i=1;i<=q;i++)scanf("%d%d",&b,&n),d.push_back(mp(b,n));sort(d.begin(),d.end());for(int i=1;i<=q;i++)if(d[i].second>d[i+1].second || d[i+1].second-d[i].second>d[i+1].first-d[i].first)return printf("unfair\n"),0;for(int k=0;k<32;k++){int res=0;for(int i=1;i<=q+1;i++){int cnt=0;for(int j=d[i-1].first+1;j<=d[i].first;j++)cnt+=bool((1<<(j%5))&k);res+=min(cnt,d[i].second-d[i-1].second);}if(res<nn/5*__builtin_popcount(k))return printf("unfair\n"),0;}printf("fair\n");return 0; }View Code
转载于:.html
更多推荐
Educational Codeforces Round 8
发布评论