CodeCraft-20 (Div. 2)
比赛链接：CodeCraft-20 (Div. 2)
A. Grade Allocation
题意：啊懒得说了
分析：啊懒得分析了
#include
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
const int mod=1e9+7;
const ll INF=1e18;
int a[maxn];
void rua()
{int n,m,sum=0;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i];int ans=min(sum,m);ans=max(a[1],ans);printf("%d\n",ans);
}
int main()
{int t;scanf("%d",&t);while(t--) rua();return 0;
}
B. String Modification
题意：相邻的1..n位反转，求反转后字典序最小的；
分析：手画一下就知道，反转后的字符串就是先后面一段，根据奇偶决定前面的一段是正着还是倒着姐在后面；
#include
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
const int mod=1e9+7;
const ll INF=1e18;
char a[maxn];
void rua()
{int n,ans=1;scanf("%d",&n);scanf("%s",a+1);int flag=1;string s1="";for(int i=1;i<=n;i++) s1+=a[i];//cout<a[i+1]) {flag=0;break;}if(flag) {printf("%s\n1\n",a+1);return;}for(int i=1;i<=n;i++){string s2="",s3="";for(int j=i;j<=n;j++) s2+=a[j];if((n-i)%2==1) for(int j=1;j0;j--) s3+=a[j];s2+=s3;if(s2 C. Primitive Primes
题意：gcd(a[i])==0 gcd(b[i])==0 求这两个多项式相乘后的系数不可整除p的一个；
分析：大概是什么数学定理，但我不会证明；
#include
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
const int mod=1e9+7;
const ll INF=1e18;
inline int read(){int x=0,flag=0;char c=getchar();while(!isdigit(c)){if(c=='-') flag=1;c=getchar();}while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return flag?-x:x;
}
inline void write(ll x){if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar(x%10+'0');
}
void rua()
{int n,m,p,s1,s2;n=read();m=read();p=read();for(int i=1;i<=n;i++) {int x;x=read();if(x%p) s1=i;}for(int i=1;i<=m;i++){int x;x=read();if(x%p) s2=i;}printf("%d\n",s1+s2-2);
}
int main()
{rua();return 0;
} D. Nash Matrix
题意：一个n*n的矩阵，对[i,j]的描述是[x,y]：如果x=y=-1，表示从[i,j]开始的点无法停止，否则表示从[i,j]开始的点在[x,y]停止，构造这样一个矩阵；
分析：如果[x,y]=[i,j]，则这里一定是X，考虑从这里开始dfs，过程是：check所有能到达的点是否有同样的终点，如果有就填下操作，并从这个点继续dfs；如果[x,y]=-1，那么就在四周找有没有-1，-1的路径要么是一个循环，要么是将要加入循环；
#include
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=1000+7;
const int mod=1e9+7;
const ll INF=1e18;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
char dd[]="DURL";
int n,pos[maxn][maxn];
char ans[maxn][maxn];
bool check(int x,int y)
{if(x<1 || y<1 || x>n || y>n) return false;return true;
}
void dfs(int x,int y,int c)
{if(ans[x][y]!='\0') return;ans[x][y]=c;for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(!check(xx,yy)) continue;if(pos[xx][yy]==pos[x][y]) dfs(xx,yy,dd[i^1]);}
}
bool rua()
{scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){int x,y;scanf("%d%d",&x,&y);if(x==-1 && y==-1) {pos[i][j]=-1;continue;}pos[i][j]=(x-1)*n+y;}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(pos[i][j]==(i-1)*n+j) dfs(i,j,'X');else if(pos[i][j]==-1){for(int k=0;k<4;k++){if(ans[i][j]!='\0') break;int xx=i+dx[k],yy=j+dy[k];if(!check(xx,yy)) continue;if(pos[xx][yy]!=-1) continue;ans[i][j]=dd[k];if(ans[xx][yy]=='\0') ans[xx][yy]=dd[k^1];}}}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) if(ans[i][j]=='\0') return false;return true;
}
int main()
{if(rua()==false) printf("INVALID\n");else{printf("VALID\n");for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) printf("%c",ans[i][j]);printf("\n");}}return 0;
} E. Team Building
题意：n个人，一场比赛有m个位置，需要k个观众，给出每个人当观众的收益和每个人在每个位置的收益，求最大收益；
分析：对观众收益从大到小排序，dp[i][j]表示前i个人在每个位置是否有人的状态j下的最大收益；
#include
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
const int mod=1e9+7;
const ll INF=1e18;
int n,m,k;
int cnt[(1<<8)+10];
ll f[maxn][(1<<8)+10];
struct node{int x,kk;} p[maxn];
bool cmp(node a,node b) {return a.x>b.x;}
int a[maxn][10];
int vis[maxn];
void init()
{for(int i=1;i<(1<>=1;}cnt[i]=num;}
}
void rua()
{scanf("%d%d%d",&n,&m,&k);init();for(int i=1;i<=n;i++){scanf("%d",&p[i].x);p[i].kk=i;}sort(p+1,p+1+n,cmp);for(int i=1;i<=n;i++) vis[p[i].kk]=i;for(int i=1;i<=n;i++)for(int j=0;jcnt[j] && i<=cnt[j]+k) f[i][j]=f[i-1][j]+p[i].x;else f[i][j]=f[i-1][j];}for(int j=0;j>j)&1)) {f[i][l]=max(f[i][l],f[i-1][l^(1<
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！