Codeforces Round #571 (Unrated for Div. 1+Div. 2)

A

略

B

被删了，被这个假题搞自闭了，显然没做出来。

C

开始莽了个NTT，后来发现会TLE，其实是个SB前缀和，对于这题，我无**说。

#include
using namespace std;
const int N=1e6+7,mod=998244353;
int n,m,ans,sum,s[N];
char a[N],b[N];
int main()
{scanf("%s",a+1),n=strlen(a+1);scanf("%s",b+1),m=strlen(b+1);for(int i=1;i<=n;i++)s[i]=s[i-1]+(a[i]!=a[i-1]);for(int i=1;i<=m;i++)sum+=a[i]!=b[i];sum&=1;ans+=sum^1;for(int i=m+1;i<=n;i++){sum+=s[i]-s[i-m];sum&=1;ans+=sum^1;}printf("%d",ans);
}

D

我的做法是这样的：对于非整数，显然先把其下取整，发现比0小多少，然后发现能加几个值，贪心加即可。

#include
using namespace std;
const int N=1e5+7;
int n,tot,a[N],b[N];
double sum;
double down(double x)
{double ret=0;if(x>=0)ret=trunc(x);else ret=trunc(x)-1;sum+=x-ret;return ret;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){double x;scanf("%lf",&x);if(trunc(x)==x)a[i]=x;else a[i]=down(x),b[i]=1;}tot=sum+1e-8;for(int i=1;i<=n&&tot;i++)if(b[i])tot--,a[i]++;for(int i=1;i<=n;i++)printf("%d\n",a[i]);
}

E

很容易发现每个(2n)*(2m)的矩阵和是一样的，不如直接扩展成(2n)*(2m)，然后直接做一下就行了

#include
using namespace std;
typedef long long ll;
const int N=2019;
int n,m,Q,s[N][N];
char str[N];
ll calc(int x,int y)
{ll ret=(1ll*x*y-1ll*(x%n)*(y%m))/2;int t=x/n^y/m,num=0;while(t)num+=t&1,t>>=1;if(num&1)ret+=(x%n)*(y%m)-s[x%n][y%m];else ret+=s[x%n][y%m];return ret;
}
int main()
{scanf("%d%d%d",&n,&m,&Q);for(int i=1;i<=n;i++){scanf("%s",str+1);for(int j=1;j<=m;j++)s[i][j]=s[i+n][j+m]=str[j]-'0',s[i+n][j]=s[i][j+m]=s[i][j]^1;}n<<=1,m<<=1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];while(Q--){int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);printf("%I64d\n",calc(c,d)+calc(a-1,b-1)-calc(a-1,d)-calc(c,b-1));}
}

F

显然从度数最小的点开始分配，然后贪心分配，即两端的点度数都不满就分配。然后xjb乱证明一通：∵Σdeg[i]=2m，所以Σ(deg[i]+1)/2<=Σdeg[i]/2+n<=m+n，于是发现每次分配度数不满的做法是可行的。

#include
using namespace std;
const int N=1e6+7;
struct node{int u,v;};
bool operator<(node a,node b){return a.v>b.v;}
priority_queueq;
int n,m,cnt,ret,tot,hd[N],v[N<<1],nxt[N<<1],w[N<<1],mark[N],vis[N],deg[N],now[N],U[N],V[N];
void adde(int x,int y,int z){v[++cnt]=y,nxt[cnt]=hd[x],w[cnt]=z,hd[x]=cnt;}
int main()
{scanf("%d%d",&n,&m);for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),U[i]=x,V[i]=y,adde(x,y,i),adde(y,x,i),deg[x]++,deg[y]++;for(int i=1;i<=n;i++)now[i]=deg[i];ret=m;for(int i=1;i<=n;i++)q.push((node){i,deg[i]});while(!q.empty()){if(ret<=(n+m+1)/2)break;int u=q.top().u;q.pop();if(vis[u])continue;vis[u]=1;for(int i=hd[u];i&&now[u]!=(deg[u]+1)/2;i=nxt[i])if(!mark[w[i]]&&now[v[i]]!=(deg[v[i]]+1)/2){now[v[i]]--,now[u]--,ret--;mark[w[i]]=1;q.push((node){v[i],now[v[i]]});}}for(int i=1;i<=m;i++)if(!mark[i])tot++;printf("%d\n",tot);for(int i=1;i<=m;i++)if(!mark[i])printf("%d %d\n",U[i],V[i]);
}

转载于:https://www.cnblogs.com/hfctf0210/p/11104352.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！