當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

codeforces 1097 Hello 2019

發(fā)布時間：2024/4/17 编程问答 34 豆豆

生活随笔收集整理的這篇文章主要介紹了 codeforces 1097 Hello 2019 小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

又回來了。。

A - Gennady and a Card Game

好像沒什么可說的了。

#include<bits/stdc++.h> using namespace std;char gc() {static char buf[100000],*p1,*p2;return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin))?EOF:*p1++;return getchar(); }template<class T> int read(T &ans) {T f=1;char ch=gc();while(!isdigit(ch)) {if(ch==EOF) return EOF;if(ch=='-') f=-1;ch=gc();}while(isdigit(ch))ans=ans*10+ch-'0',ch=gc();ans*=f;return 1; }template<class T1,class T2> int read(T1 &a,T2 &b) {return read(a)==EOF?EOF:read(b); }template<class T1,class T2,class T3> int read(T1 &a,T2 &b,T3 &c) {return read(a,b)==EOF?EOF:read(c); }const int Maxn=110000; const int inf=0x3f3f3f3f;char a[Maxn],s[Maxn];int main() {scanf("%s",a);for(int i=1;i<=5;i++) {scanf("%s",s);if(a[0]==s[0]||a[1]==s[1]) return 0*puts("YES");}puts("NO");return 0; }

B - Petr and a Combination Lock

這個當然可以DP一下，不過暴力枚舉是能過的。

C - Yuhao and a Parenthesis

首先按照括號序列的套路求前綴和，一個序列要么只能做前綴，要么只能做后綴，要么兩個都能做或都不能做。

那么只要記一下就好了，都能做的數(shù)目要除以2。

D - Makoto and a Blackboard

這題我剛開始想插板，但是最后發(fā)現(xiàn)前面的決策對后面有影響，所以不能插板。但是聽說暴力DP可以過？于是寫了個暴力。

#include<bits/stdc++.h> using namespace std;char gc() { // static char buf[100000],*p1,*p2; // return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin))?EOF:*p1++;return getchar(); }template<class T> int read(T &ans) {T f=1;char ch=gc();while(!isdigit(ch)) {if(ch==EOF) return EOF;if(ch=='-') f=-1;ch=gc();}while(isdigit(ch))ans=ans*10+ch-'0',ch=gc();ans*=f;return 1; }template<class T1,class T2> int read(T1 &a,T2 &b) {return read(a)==EOF?EOF:read(b); }template<class T1,class T2,class T3> int read(T1 &a,T2 &b,T3 &c) {return read(a,b)==EOF?EOF:read(c); }typedef long long ll; const int Maxn=1100000; const int inf=0x3f3f3f3f; const ll mod=1000000007;ll n,f[2][Maxn],k,inv[Maxn];ll powp(ll a,ll b) {ll ans=1;while(b) {if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans; }int main() {read(n,k);ll ans=1;inv[0]=inv[1]=1;for(int i=2;i<=1000;i++) inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;for(ll i=2;i*i<=n;i++)if(n%i==0) {int temp=0;while(n%i==0) {temp++;n/=i;}int now=0;for(int j=0;j<temp;j++) f[0][j]=0;f[0][temp]=1;for(int j=1;j<=k;j++) {now^=1;ll tempp=0;for(int l=temp;l>=0;l--)f[now][l]=tempp=(tempp+f[now^1][l]*inv[l+1]%mod)%mod;}ll sxz=0;for(ll j=0;j<=temp;j++)sxz+=f[now][j]*powp(i,j)%mod;sxz%=mod;ans=ans*sxz%mod;}if(n!=1) {int temp=1;int now=0;for(int j=0;j<=temp;j++) f[0][j]=0;f[0][temp]=1;for(int j=1;j<=k;j++) {now^=1;ll tempp=0;for(int l=temp;l>=0;l--)f[now][l]=tempp=(tempp+f[now^1][l]*inv[l+1]%mod)%mod;}ll sxz=0;for(ll j=0;j<=temp;j++) sxz+=f[now][j]*powp(n,j)%mod;sxz%=mod;ans=ans*sxz%mod;}printf("%I64d",ans);return 0; }

E - Egor and an RPG game

膜拜一下題解

%%% Radewoosh %%%

那么我們直接模擬即可。

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cctype> #define qmin(x,y) (x=min(x,y)) #define qmax(x,y) (x=max(x,y)) using namespace std;inline char gc() { // static char buf[100000],*p1,*p2; // return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;return getchar(); }template<class T> int read(T &ans) {ans=0;char ch=gc();T f=1;while(!isdigit(ch)) {if(ch==EOF) return -1;if(ch=='-') f=-1;ch=gc();}while(isdigit(ch))ans=ans*10+ch-'0',ch=gc();ans*=f;return 1; }template<class T1,class T2> int read(T1 &a,T2 &b) {return read(a)!=EOF&&read(b)!=EOF?2:EOF; }template<class T1,class T2,class T3> int read(T1 &a,T2 &b,T3 &c) {return read(a,b)!=EOF&&read(c)!=EOF?3:EOF; }typedef long long ll; const int Maxn=210000; const int inf=0x3f3f3f3f;int a[Maxn],b[Maxn],pre[Maxn],res[Maxn],n,vis[Maxn],top,ans;void work(int x) {if(x==0) return;int zhy=0;for(int i=1;i<=x;i++) pre[i]=0;b[++zhy]=1;for(int i=2;i<=x;i++) {int l=1,r=zhy,mid=l+r>>1,nh=0;while(l<=r) {if(a[i]>=a[b[mid]]) nh=mid,l=mid+1;else r=mid-1; mid=l+r>>1;}pre[i]=b[nh];if(nh==zhy) b[++zhy]=i;else b[nh+1]=i;}if(1ll*zhy*(zhy+1)/2>x) {ans++;for(int i=1;i<=x;i++) vis[i]=0;int now=b[zhy],&len=res[++top];while(now) {vis[now]=1;res[++top]=a[now];len++;now=pre[now];}reverse(res+top-len+1,res+top+1);now=0;for(int i=1;i<=x;i++)if(!vis[i]) a[++now]=a[i];work(now);}else {for(int i=1;i<=x;i++) pre[i]=0;zhy=0;b[++zhy]=1;for(int i=2;i<=x;i++) {int l=1,r=zhy,mid=l+r>>1,nh=0;while(l<=r) {if(a[i]<=a[b[mid]]) nh=mid,r=mid-1;else l=mid+1; mid=l+r>>1;}pre[b[nh]]=i;if(nh) b[nh]=i;else b[++zhy]=i;}for(int i=1;i<=x;i++) vis[i]=0;for(int i=1;i<=x;i++)if(!vis[i]) {ans++;int now=i,&len=res[++top];while(now) {vis[now]=1;res[++top]=a[now];len++;now=pre[now];}}} }signed main() { // freopen("test.in","r",stdin); // freopen("out","w",stdout);int t; read(t);while(~read(n)) {for(int i=1;i<=n;i++) read(a[i]);top=ans=0; work(n);printf("%d\n",ans);int temp=1;for(int i=1;i<=ans;i++) {int len=res[temp++];printf("%d",len);while(len--) printf(" %d",res[temp++]);puts("");}for(int i=1;i<=temp;i++) res[i]=0;}return 0; }

F - Alex and a TV Show

如果沒有3操作的話，那就直接開bitset就好了。

那么我們考慮3操作。如果我們在bitset里面存的不是原數(shù)，而是把原數(shù)的質(zhì)因子都設成1的話，那么我們發(fā)現(xiàn)，1,2操作都沒有變化，而3操作可以直接&起來，但是輸出的時候就不太好辦了。解決方法就是容斥一下，注意要預處理好容斥的系數(shù)，不然復雜度會爆。

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<bitset> #include<cctype> #define qmin(x,y) (x=min(x,y)) #define qmax(x,y) (x=max(x,y)) using namespace std;inline char gc() { // static char buf[100000],*p1,*p2; // return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;return getchar(); }template<class T> int read(T &ans) {ans=0;char ch=gc();T f=1;while(!isdigit(ch)) {if(ch==EOF) return -1;if(ch=='-') f=-1;ch=gc();}while(isdigit(ch))ans=ans*10+ch-'0',ch=gc();ans*=f;return 1; }template<class T1,class T2> int read(T1 &a,T2 &b) {return read(a)!=EOF&&read(b)!=EOF?2:EOF; }template<class T1,class T2,class T3> int read(T1 &a,T2 &b,T3 &c) {return read(a,b)!=EOF&&read(c)!=EOF?3:EOF; }typedef long long ll; const int Maxn=110000; const int inf=0x3f3f3f3f;bitset<7001> a[7001],b[7001],c[Maxn]; int miu[Maxn],bj[Maxn],p[Maxn],tot,n,q,x,u,v,opt;void ycl() {miu[1]=1;for(int i=2;i<=7000;i++) {if(!bj[i]) {p[++tot]=i;miu[i]=1;}int j=0,temp;while(j++,(temp=i*p[j])<=7000) {bj[temp]=1;if(i%p[j]==0) break;miu[temp]=miu[i];}}for(int i=1;i<=7000;i++)for(int j=i;j<=7000;j+=i)a[j].set(i),b[i].set(j,miu[j/i]); }signed main() { // freopen("test.in","r",stdin);ycl();read(n,q);while(q--) {read(opt,x);switch(opt) {case 1 : read(v),c[x]=a[v];break;case 2 : read(u,v),c[x]=c[u]^c[v];break;case 3 : read(u,v),c[x]=c[u]&c[v];break;case 4 : read(v),putchar('0'+((c[x]&b[v]).count()&1));}}return 0; }

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

總結

以上是生活随笔為你收集整理的codeforces 1097 Hello 2019的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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

Codeforces

上一篇： 2、python机器学习基础教程——K近
下一篇： python print()内置函数