A：http://codeforces.com/contest/1355/problem/A
题意：
每次加这个数每一位的最大和最小的乘积，求第K次的结果。
解析：
直接模拟即可，但是有一个TLE点，就是当最大或最小=0时，就需要终止了，因为再加下去值就不变了。
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<set> #include<map> #include<cmath> #include<queue> typedef long long ll; using namespace std; const int maxn=2e5+10; int a[maxn]; int main() { int t; cin>>t; while(t--) { int n; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; int cnt=0; sort(a,a+n); int sum=0; for(int i=0;i<n;i++) { cnt++; if(cnt==a[i]) { sum++; cnt=0; } } cout<<sum<<endl; } }
B：http://codeforces.com/contest/1355/problem/B
题意：
分组，每个人的e值不能大于当前组人数，求最大组数。
解析：
贪心取，当前组人数==e[]时，就算一个组，组数++，组人数清0。
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<set> #include<map> #include<cmath> #include<queue> typedef long long ll; using namespace std; const int maxn=2e5+10; int a[maxn]; int main() { int t; cin>>t; while(t--) { int n; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; int cnt=0; sort(a,a+n); int sum=0; for(int i=0;i<n;i++) { cnt++; if(cnt==a[i]) { sum++; cnt=0; } } cout<<sum<<endl; } }
C：http://codeforces.com/contest/1355/problem/C
题意：A<=x<=B<=y<=C<=z<=D，三个区间各取一个数构成三角形，求种类数。
解析：
差分数组+前缀和解法：
首先x+y>z才能是一个三角形。
那么如果知道了x+y的种类数，那么直接枚举x+y>c的c的数目，就是答案。
用差分数组来记录a+b的种类数。对于一个x，x+y的范围就是：[x+b,x+c]。
这里通过差分数组维护，然后通过两次前缀和还原。对于c<=i<=d的i，x[maxn-1]-x[i]就是a+b>c的数目，累加即可。
#include<iostream> #include<cstring> #include<map> #include<cstdio> using namespace std; typedef long long ll; const int maxn=1e6+10; ll x[maxn]; int main() { ll a,b,c,d; cin>>a>>b>>c>>d; for(int i=a;i<=b;i++) { x[i+b]++; x[i+c+1]--; } for(int i=1;i<maxn;i++) x[i]+=x[i-1]; for(int i=1;i<maxn;i++) x[i]+=x[i-1]; ll cnt=0; for(int i=c;i<=d;i++) cnt+=x[maxn-1]-x[i]; cout<<cnt<<endl; }
枚举：
如果确定了x+y而且确定了x,那么y是确定的。所以x的数目*z的数目，就是答案。通过枚举x+y，此时可取的c的数目为：min(i-1,d)-c+1。x的数目，需要通过区间：
x+y=m
y=m-x
B<=m-x<=C
m-C<=x<=m-B
又A<=x<=B
所以这里取个交集即可，即为可取的x的数目。
x的数目*c的数目，累加即可。
#include<iostream> #include<cstring> #include<map> #include<cstdio> using namespace std; typedef long long ll; const int maxn=1e6+10; ll x[maxn]; int main() { ll a,b,c,d; cin>>a>>b>>c>>d; ll sum=0; for(ll i=a+b;i<=c+d;i++) { ll m1=min(i-1,d)-c+1; ll m2=min(i-b,b)-max(i-c,a)+1; if(m1<0||m2<0) continue; sum+=m1*m2; } cout<<sum<<endl; }
D：http://codeforces.com/contest/1355/problem/D
题意：
构造一个含有n个数，和为s的数组，能否找到一个K，使得没有子序列的和为K或者S-K。
解析：
先放n-1个1，最后一个是s-(n-1)
那么我们假设k为n，可以保证前n-1个1加不到n。
如果n>(s-n+1)
有子序列和范围：[s-n+1,s]
n>=s-n+1，很明显，n在范围里面，就算前n-1个1加不到n，s-n也还是可以被加到。
如果n<(s-n+1)
就可以保证s-n不会被加到
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<set> #include<map> #include<cmath> #include<queue> typedef long long ll; using namespace std; const int maxn=2e5+10; int a[maxn]; int main() { int n,s; cin>>n>>s; if(n==s) cout<<"NO"<<endl; else { int md=n-1; int md2=s-(n-1); if(md+1>=md2) cout<<"NO"<<endl ; else { cout<<"YES"<<endl; for(int i=1;i<n;i++) cout<<"1"<<" "; cout<<md2<<endl; cout<<n<<endl; } } }