Educational Codeforces Round 84 (Rated for Div. 2)
题意：给出n，问是否能由k个奇数相加得出。
解析：如果k是偶数，那么k个奇数相加，结果只能为偶数不能为奇数。相同的，k是奇数，那么奇数个奇数相加，结果只能为奇数。所以n,k需要同一个奇偶性。k个奇数相加，最小的一个构造就是1+3+5+7+....等差数列，k个的和就是k*k，如果n<k*k这个最低标准，肯定不能构造出来的。所以n>=k*k。满足以上条件即可。
#include<iostream> #include<cstdio> using namespace std; typedef long long ll; int main() { int t; cin>>t; while(t--) { ll n,k; cin>>n>>k; if(n%2==0&&k%2==0&&n>=k*k) cout<<"YES"<<endl; else if(n%2!=0&&k%2!=0&&n>=k*k) cout<<"YES"<<endl; else cout<<"NO"<<endl; } }
题意：题挺长的。简单来讲就是n个公主，n个王子。给出n行，k个数表示第i个公主的想要人选。这些人选的编号是递增的，公主只能选最小的而且没有被选择的王子。问是否可以再增加一对？可以的话输出任意一对即可。
解析：暴力模拟，但是开两个memset会超时。开一个w[]就可以了，w[i]=x说明x公主和i王子配对。记录未配对的情况时，这个公主编号可以在输入时直接判断得出，所以不需要两个数组来记录配对情况。王子的结尾for一遍就好了。看我....别说了都是泪
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; const int maxn=1e5+10; int w[maxn]; int main() { int t; scanf("%d",&t); while(t--) { int n; memset(w,0,sizeof(w)); scanf("%d",&n); int l=-1,r=-1; for(int i=1;i<=n;i++) { int k; scanf("%d",&k); int x; int mid=0; for(int j=0;j<k;j++) { scanf("%d",&x); if(!mid&&w[x]==0) { w[x]=1; mid=1; } } if(!mid) l=i; } for(int i=1;i<=n;i++) { if(w[i]==0) { r=i;break; } } if(l!=-1&&r!=-1) { cout<<"IMPROVE"<<endl; cout<<l<<" "<<r<<endl; } else cout<<"OPTIMAL"<<endl; } }
题意：一个n*m棋盘，给出k个起始点，k个对应目标点，要求给出一个移动方式，每次让这K个同时移动，保证每个点至少经过目标点一次。
解析：路径长度不超过2*n*m，这个步数，完全可以把整个图遍历两遍，所以必然有解，不存在无解的情况。最优解是几乎不可能写出来的，而且题意并没有要求最优解。所以我们把所有的点堆到一个角，我这边是左上角。然后蛇形走位，遍历全图，就可以保证访问到目标点了。注意这个x,y的范围，它实际上是这样的一个图，L,R,U,D不太常规，注意一下即可：
这里说一下，string(n,'S')比常规for赋值快得多！
#include <bits/stdc++.h> using namespace std; int main() { int n,m,k; cin>>n>>m>>k; int x,y; for(int i=1;i<=k;i++) cin>>x>>y; for(int i=1;i<=k;i++) cin>>x>>y; string ch=""; ch+=string(n-1,'U'); ch+=string(m-1,'L'); for(int i=1;i<=m;i++) { if(i%2!=0) { for(int j=1;j<=n-1;j++) ch+='D'; } else for(int j=1;j<=n-1;j++) ch+='U'; if(i<m) ch+='R'; } cout<<ch.length()<<endl; cout<<ch<<endl; }