A:http://codeforces.com/contest/1371/problem/A
题意:
1~n个棒子,长度依次为1~n。可两两合成,求能得到的最多相同长度棒子数。
解析:
偶数,直接/2即可。
奇数,比如对5,
1,2,3,4,5
1~4,可合成为:5,5,加上末尾5,结果为3。
所以奇数时为n/2+1
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int maxn=2e5+10; int main() { // 4 0 20 int t; cin>>t; while(t--) { ll n; cin>>n; if(n%2==0) cout<<n/2<<endl; else { cout<<n/2+1<<endl; } } }
B:http://codeforces.com/contest/1371/problem/B
题意:
n天,r:一周的天数依次定为1~r,即1<=k<=r
问所能组成的不同图案数。要求是每个块都不能被孤立,两两要相邻。
解析:
当n>r时,对于每一个k来讲,种类数==k,即k=1,1种,k=2,2种......
所以,这种情况,直接等差数列求和:(r*r+r)/2
当n<=r时,画图得出,r==n时,算一种,r>n时,没有其他情况了,因为一周的天数>n,n除了排成一排,是不能再换行了,两两必须要相邻。
所以这个时候,等差数列求和求到n-1项,再+1即可。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; int main() { // 4 0 20 int t; cin>>t; while(t--) { ll n,r; cin>>n>>r; if(n>r) cout<<(r*r+r)/2<<endl; else { ll md=n-1; cout<<(md*md+md)/2+1<<endl; } } }
C:http://codeforces.com/contest/1371/problem/C
题意:
a个香草,b个巧克力。
两种客人,分别n个,m个。
设v个香草,c个巧克力。
v>c,第一种客人吃香草,否则吃巧克力。
v>c,第二种客人吃巧克力,否则吃香草。
问是否有这么一种进场顺序,能保证所有人都有得吃。
解析:
可以看出,第一种客人,吃多的那一方,第二种客人,吃较少的那一方,
所以看第二种客人:对于初始较少的一方,吃完后,他们就没得吃了,所以为了每个人都有的吃,min(a,b)>=m
假设min(a,b)==b,当b==m时,需要a>=n
当b>m时,a+b-m>=n
总的来讲,就是:a+b>=n+m
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int maxn=2e5+10; int main() { // 4 0 20 int t; cin>>t; while(t--) { ll a,b,n,m; cin>>a>>b>>n>>m; if(min(a,b)>=m&&a+b>=n+m) cout<<"YES"<<endl; else cout<<"NO"<<endl; } }
D:http://codeforces.com/contest/1371/problem/D
题意:
构造n*n的01矩阵,要求包含k个1
使得f=(含1最大行-最小)^2+(含1最大列-最小)^2最小。
解析:
第一时间想到的,肯定是平均放。之前做过类似的:
当k%n==0的时候,f一定为0,直接按上图放即可。
k%n!=0时,f一定为1^2+1^2。因为先平均放后,余数依次往上加,一定能保证最大与最小的差距为1。
令b=k/n,yu=k%n
前yu行,每行放b+1个,其他的行均放b个,即可。
#include<iostream> #include<set> #include<cstring> #include<algorithm> using namespace std; const int maxn=4e2;int a[maxn][maxn]; int main() { int t; cin>>t; while(t--) { int n,k; cin>>n>>k; memset(a,0,sizeof(a)); if(k%n==0) cout<<"0"<<endl; else cout<<"2"<<endl; int yu=k%n; int b=k/n; for(int i=0;i<yu;i++) for(int j=i;j<=i+b;j++) a[i][j%n]=1; for(int i=yu;i<n;i++) for(int j=i;j<b+i;j++) a[i][j%n]=1; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) cout<<a[i][j]; cout<<endl; } } }