Codeforces Round #584 - Dasha Code Championship - Elimination Round (rated, open for everyone, Div. 1 + Div. 2) 题解
A.Paint the Numbers
◆题目传送门◇
题目大意
给定NNN个数的数列AAA，若当Ai≡0(mod  Aj)A_i\equiv 0(\mod A_j)Ai?≡0(modAj?)，则AiA_iAi?和AjA_jAj?可以分到同一类，求最少有多少类。
分析
水题，暴力模拟即可。
参考代码
#include<cstdio>
#include<algorithm>
using namespace std;const int Maxn=100; int N,A[Maxn+5];
bool vis[Maxn+5];int main() {
#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d",&N);for(int i=1;i<=N;i++)scanf("%d",&A[i]);sort(A+1,A+N+1);for(int i=1;i<=N;i++)if(!vis[i])for(int j=i+1;j<=N;j++)if(A[j]%A[i]==0)vis[j]=true;int cnt=0;for(int i=1;i<=N;i++)if(!vis[i])cnt++;printf("%d\n",cnt); return 0;
}
B.Koala and Lights
◆题目传送门◇
题目大意
对于NNN盏灯，每盏灯有两个属性ai,bia_i,b_iai?,bi?，表示第iii盏灯从零时刻开始在bib_ibi?时刻变一次（由开到关或由关到开），此后每隔aia_iai?秒变化一次。求最多有多少盏灯是打开的。
分析
我TM比赛时想了一个多小时才想出来QAQ…(脑子进水了。。。
通过一波证明可以发现最多125秒后就会出现循环。。。（我实在不会证明，有人会证的话请在评论区补一下 ：-）
参考代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int Maxn=100;
const int M=100000;int N,A[Maxn+5],B[Maxn+5];
int f[Maxn+5];int main() {
#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifchar s[Maxn+5];scanf("%d %s",&N,s+1);for(int i=1;i<=N;i++)scanf("%d %d",&A[i],&B[i]);int ans=0;for(int i=1;i<=N;i++) {
f[i]=s[i]-'0';ans+=f[i];}for(int tim=1;tim<=M;tim++) {
for(int i=1;i<=N;i++)if(tim>=B[i]&&(tim-B[i])%A[i]==0)f[i]=(!f[i]);int tmp=0;for(int i=1;i<=N;i++)tmp+=f[i];ans=max(ans,tmp);}printf("%d\n",ans);return 0;
}
C.Paint the Digits
◆题目传送门◇
题目大意
将一个由数字0到9组成的字符串分成两部分，要求将第一部分的所有数按顺序取出来之后接上第二部分的所有按顺序取出的数，若能够形成一个最长不下降子序列则输出一个方案，否则输出-。
分析
参考代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int Maxn=2e5;int N;
char s[Maxn+5],s1[Maxn+5];
bool vis[Maxn+5];int main() {
#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifint _;scanf("%d",&_);while(_--) {
scanf("%d %s",&N,s);memcpy(s1,s,sizeof s);memset(vis,false,sizeof vis);sort(s1,s1+N);char mn=255;int pos=0;for(int i=0;i<N;i++)if(mn>s[i])mn=s[i],pos=i;int len=0;for(int i=pos;i<N;i++)if(s1[len]==s[i])vis[i]=true,++len;bool flag=true;for(int i=0;i<N;i++)if(!vis[i]) {
if(s[i]!=s1[len]) {
flag=false;break;}len++;}if(!flag) {
puts("-");continue;}for(int i=0;i<N;i++)putchar(vis[i]?'1':'2');puts("");}return 0;
}
D.Cow and Snacks
◆题目传送门◇
题目大意
有KKK个人分享NNN种零食，每个人有两种喜欢的零食。现在将所有人排成一排，一个人拿着NNN种零食从前往后走，每个人会吃掉他所喜欢的所有零食，若一种也没吃掉就很沮丧。求最少的沮丧的人数。
分析
考虑将每个人所喜欢的零食连起来，这样问题就变成了一个图论问题。
对于一个含有ccc个点的连通块，我们可以发现它最多可以满足c?1c-1c?1个人。
那么我们记CCC为连通块的个数，nnn为出现的零食的个数，则答案为K?n+CK-n+CK?n+C。
参考代码
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;const int Maxn=1e5;vector<int> G[Maxn+5];
inline void addedge(int u,int v) {
G[u].push_back(v),G[v].push_back(u);
}
int N,K;
bool vis[Maxn+5],used[Maxn+5];void DFS(int u) {
vis[u]=true;for(int i=0;i<(int)G[u].size();i++)if(!vis[G[u][i]])DFS(G[u][i]);
}int main() {
#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d %d",&N,&K);int cnt=0;for(int i=1;i<=K;i++) {
int x,y;scanf("%d %d",&x,&y);addedge(x,y);if(!used[x])cnt++;if(!used[y])cnt++;used[x]=used[y]=true;}int ans=0;for(int i=1;i<=N;i++)if(used[i]&&!vis[i])DFS(i),ans++;printf("%d\n",K-cnt+ans);return 0;
}
E1.Rotate Columns (easy version)
◆题目传送门◇
题目大意
给定一个N×MN\times MN×M的矩阵，你可以对每一列的数字进行任意次的旋转操作（即整体向上或者整体向下）。输出在做出任意次旋转操作后每一行的最大值之和。
分析
考虑到NNN很小，我们用状压DP解决。
设状态f(i,S)f(i,S)f(i,S)为当前在对第iii列进行旋转操作，对于SSS中的行已经计算出答案的情况。
对于每一列，我们暴力旋转NNN次，每次暴力转移即可。
参考代码
用E2的代码就可以了。
可以去掉这个排序的部分。
E2.Rotate Columns (hard version)
◆题目传送门◇
题目大意
同E1，只是数据范围更大。
分析
在E1的基础上，我们考虑贪心。
显然我们可以用每列上的最大值来比较每一列，这样的话我们只需要转这几列即可。
具体还是看代码吧。。。
参考代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int Maxn=12;
const int Maxm=2000;int N,M;
int A[Maxn+5][Maxm+5];
struct Node {
int key,id;
};
bool operator < (Node lhs,Node rhs){
return lhs.key>rhs.key;}
Node t[Maxm+5];int f[(1<<Maxn)+5],t1[(1<<Maxn)+5],t2[(1<<Maxn)+5];
bool used[Maxm+5];int main() {
#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifint _;scanf("%d",&_);while(_--) {
scanf("%d %d",&N,&M);for(int i=1;i<=M;i++)t[i].id=i,t[i].key=0,used[i]=false;for(int i=0;i<N;i++)for(int j=1;j<=M;j++) {
scanf("%d",&A[i][j]);t[j].key=max(t[j].key,A[i][j]);}sort(t+1,t+M+1);for(int i=1;i<=M&&i<=N;i++)used[t[i].id]=true;memset(f,0,sizeof f);for(int i=1;i<=M;i++) {
if(!used[i])continue;for(int s=0;s<(1<<N);s++)t1[s]=0;for(int j=1;j<=N;j++) {
for(int s=0;s<(1<<N);s++)t2[s]=f[s];for(int s=0;s<(1<<N);s++)for(int k=0;k<N;k++)if(!(s&(1<<k)))t2[s|(1<<k)]=max(t2[s|(1<<k)],t2[s]+A[k][i]);int tmp=A[0][i];for(int k=0;k<N-1;k++)A[k][i]=A[k+1][i];A[N-1][i]=tmp;for(int s=0;s<(1<<N);s++)t1[s]=max(t1[s],t2[s]),t2[s]=0;}for(int s=0;s<(1<<N);s++)f[s]=t1[s];}printf("%d\n",f[(1<<N)-1]);}return 0;
}