总结：题目很难读，只能靠样例理解，也不知道代码写得对不对，万幸数据不太强。
A
给一个多项式的因式分解的形式，比如P=(x-a1)(x-a2)...(x-an)，要求出多项式除了x^n之外，其他项的系数。n<=10。
比如x^2，就是选2项共享一个x，其他项贡献ai乘起来，所以dfs搜一下。
//
// Created by zxc on 2020/9/23.
//
#include <bits/stdc++.h>
using namespace std;
int n;
int r[15];
int res[15];
bool vis[15];
void dfs(int i,int now,int tar){
if(i==n+2){
return;
}
if(now==tar){
int t=1;
for(int j=1;j<=n;j++){
if(!vis[j]){
t=t*r[j];
}
}
res[tar]+=t;
return;
}
vis[i]=true;
dfs(i+1,now+1,tar);
vis[i]=false;
dfs(i+1,now,tar);
}
int main(){
// freopen("in.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&r[i]);
r[i]=-r[i];
}
for(int i=n-1;i>=0;i--){
dfs(1,0,i);
}
for(int i=n-1;i>=0;i--){
printf("%d%c",res[i],i==0?'
':' ');
}
return 0;
}
B
给定三个数集，大小是1e4，在三个集合里分别找三个数a，b和c，使得|a-b|+|b-c|+|c-a|最小。
这题一开始没思路放了，思路一开始不对，一直想着正负正负和大小关系，后来想枚举枚举，就想到枚举中间的数，再一看，发现如果枚举中间的数，那表达式其实就是左右两个数的距离的2倍。
所以把三个数集排一下序，然后按bac,cab,abc,cba,acb,bca这六种情况，分别枚举中间的值，然后lower_bound找到左右两边最近的一个，再注意判掉一些边界情况。题目说如果有多个输出三元组最大的，可是并没有定义什么是三元组最大的？？？猜了一下是和最大，就过了。
代码是我最喜欢的ctrl c+v
//
// Created by zxc on 2020/9/23.
//
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+50;
vector<int> a,b,c;
int as,bs,cs,x;
int ans_a,ans_b,ans_c;
struct node{
int a,b,c;
bool operator <(const node& rhs)const{
return (a+b+c)<(rhs.a+rhs.b+rhs.c);
}
};
int main(){
// freopen("in.txt","r",stdin);
scanf("%d%d%d",&as,&bs,&cs);
for(int i=0;i<as;i++){
scanf("%d",&x);
a.push_back(x);
}
for(int i=0;i<bs;i++){
scanf("%d",&x);
b.push_back(x);
}
for(int i=0;i<cs;i++){
scanf("%d",&x);
c.push_back(x);
}
sort(a.begin(),a.end());
sort(b.begin(),b.end());
sort(c.begin(),c.end());
int ans=0x3f3f3f3f;
// cab
for(int i=0;i<as;i++){
int mid=a[i];
int cx=lower_bound(c.begin(),c.end(),mid)-c.begin();
if(cx==cs){
cx--;
}else if(c[cx]!=mid){
if(cx==0){
continue;
}
cx--;
}
int cc=c[cx];
int bd=lower_bound(b.begin(),b.end(),mid)-b.begin();
if(bd==bs){
continue;
}
int bb=b[bd];
int tmp=2*(bb-cc);
if(tmp<ans){
ans=tmp;
ans_a=mid;
ans_b=bb;
ans_c=cc;
}else if(tmp==ans){
node now={ans_a,ans_b,ans_c};
node tp={mid,bb,cc};
if(now<tp){
ans_a=mid;
ans_b=bb;
ans_c=cc;
}
}
}
// bac
for(int i=0;i<as;i++){
int mid=a[i];
int bx=lower_bound(b.begin(),b.end(),mid)-b.begin();
if(bx==bs){
bx--;
}else if(b[bx]!=mid){
if(bx==0){
continue;
}
bx--;
}
int bb=b[bx];
int cd=lower_bound(c.begin(),c.end(),mid)-c.begin();
if(cd==cs){
continue;
}
int cc=c[cd];
int tmp=2*(cc-bb);
if(tmp<ans){
ans=tmp;
ans_a=mid;
ans_b=bb;
ans_c=cc;
}else if(tmp==ans){
node now={ans_a,ans_b,ans_c};
node tp={mid,bb,cc};
if(now<tp){
ans_a=mid;
ans_b=bb;
ans_c=cc;
}
}
}
// abc
for(int i=0;i<bs;i++){
int mid=b[i];
int ax=lower_bound(a.begin(),a.end(),mid)-a.begin();
if(ax==as){
ax--;
}else if(a[ax]!=mid){
if(ax==0){
continue;
}
ax--;
}
int aa=a[ax];
int cd=lower_bound(c.begin(),c.end(),mid)-c.begin();
if(cd==cs){
continue;
}
int cc=c[cd];
int tmp=2*(cc-aa);
if(tmp<ans){
ans=tmp;
ans_a=aa;
ans_b=mid;
ans_c=cc;
}else if(tmp==ans){
node now={ans_a,ans_b,ans_c};
node tp={aa,mid,cc};
if(now<tp){
ans_a=aa;
ans_b=mid;
ans_c=cc;
}
}
}
// cba
for(int i=0;i<bs;i++){
int mid=b[i];
int cx=lower_bound(c.begin(),c.end(),mid)-c.begin();
if(cx==cs){
cx--;
}else if(c[cx]!=mid){
if(cx==0){
continue;
}
cx--;
}
int cc=c[cx];
int ad=lower_bound(a.begin(),a.end(),mid)-a.begin();
if(ad==as){
continue;
}
int aa=a[ad];
int tmp=2*(aa-cc);
if(tmp<ans){
ans=tmp;
ans_a=aa;
ans_b=mid;
ans_c=cc;
}else if(tmp==ans){
node now={ans_a,ans_b,ans_c};
node tp={aa,mid,cc};
if(now<tp){
ans_a=aa;
ans_b=mid;
ans_c=cc;
}
}
}
// acb
for(int i=0;i<cs;i++){
int mid=c[i];
int ax=lower_bound(a.begin(),a.end(),mid)-a.begin();
if(ax==as){
ax--;
}else if(a[ax]!=mid){
if(ax==0){
continue;
}
ax--;
}
int aa=a[ax];
int bd=lower_bound(b.begin(),b.end(),mid)-b.begin();
if(bd==bs){
continue;
}
int bb=b[bd];
int tmp=2*(bb-aa);
if(tmp<ans){
ans=tmp;
ans_a=aa;
ans_b=bb;
ans_c=mid;
}else if(tmp==ans){
node now={ans_a,ans_b,ans_c};
node tp={aa,bb,mid};
if(now<tp){
ans_a=aa;
ans_b=bb;
ans_c=mid;
}
}
}
// bca
for(int i=0;i<cs;i++){
int mid=c[i];
int bx=lower_bound(b.begin(),b.end(),mid)-b.begin();
if(bx==bs){
bx--;
}else if(b[bx]!=mid){
if(bx==0){
continue;
}
bx--;
}
int bb=b[bx];
int ad=lower_bound(a.begin(),a.end(),mid)-a.begin();
if(ad==as){
continue;
}
int aa=a[ad];
int tmp=2*(aa-bb);
if(tmp<ans){
ans=tmp;
ans_a=aa;
ans_b=bb;
ans_c=mid;
}else if(tmp==ans){
node now={ans_a,ans_b,ans_c};
node tp={aa,bb,mid};
if(now<tp){
ans_a=aa;
ans_b=bb;
ans_c=mid;
}
}
}
printf("MinD(%d, %d, %d) = %d
",ans_a,ans_b,ans_c,ans);
return 0;
}
C
题意也是很难读。。。n个人，每个人有一个分数，然后每个人有一个合照，合照上都是同校的队友，然后现在要统计所有学校的总分按从高到低排序，每个学校的id就是最小的那个学生id，分数相同按队员数量从小到大排序，数量相同按id从小到大排序。
id是4位数，所以不用离散化，就先并查集合并一下，然后暴力枚举全部出现过的id，更新每个学校队伍的最小学生id，以及统计数量和总分，然后去重，排序。最后输出记得要%4d。
//
// Created by zxc on 2020/9/23.
//
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int p[N];
int n,k,id[N],sc[N],x;
vector<int> fr[N];
int find(int x){
return x==p[x]?p[x]:p[x]=find(p[x]);
}
int vis[N];
struct node{
int scid;
int allsco;
int num;
int fir=true;
bool operator<(const node& rhs)const{
if(allsco!=rhs.allsco){
return allsco>rhs.allsco;
}else{
if(num!=rhs.num){
return num<rhs.num;
}else{
return scid<rhs.scid;
}
}
}
bool operator ==(const node& rhs)const{
return (allsco==rhs.allsco && num==rhs.num && scid==rhs.scid && fir==rhs.fir);
}
}ans[N];
int main(){
// freopen("in.txt","r",stdin);
scanf("%d",&n);
for(int i=0;i<=9999;i++){
p[i]=i;
}
for(int i=1;i<=n;i++){
scanf("%d",&id[i]);
vis[id[i]]=true;
scanf("%d",&k);
for(int j=0;j<k;j++){
scanf("%d",&x);
vis[x]=true;
int fa=find(id[i]);
int fb=find(x);
fr[id[i]].push_back(x);
if(fa!=fb){
p[fa]=fb;
}
}
scanf("%d",&sc[id[i]]);
}
for(int i=0;i<=9999;i++){
if(!vis[i]){
continue;
}
int fa=find(i);
ans[fa].allsco+=sc[i];
ans[fa].num++;
if(ans[fa].fir){
ans[fa].scid=i;
ans[fa].fir=false;
}else{
ans[fa].scid=min(ans[fa].scid,i);
}
}
vector<node> v;
for(int i=0;i<=9999;i++){
if(!vis[i]){
continue;
}
int fa=find(i);
v.push_back(ans[fa]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
int siz=v.size();
printf("%d
",siz);
for(int i=0;i<siz;i++){
printf("%04d %d %d
",v[i].scid,v[i].num,v[i].allsco);
}
return 0;
}
D
题意不知道在讲啥。。。连个中心词coupon都看不懂，估计是优惠还是啥，反正分析样例就是有n个商品，n个级别的优惠，买一个商品可以得到一个优惠(显然是选优惠最高的)，同理买同一种的第二个商品就只能选第二档优惠，如果买超过n个同类商品，就没有优惠了。有d美元，问怎么买可以买到最多的商品。
这题卡了将近一个小时。。。最后灵光一现想到面经里面看过排序几个有序大文件里的数字，就堆里只要放每个文件的一个指针，然后拿完一个就把对应文件的指针移到下一个数。
所以同理，维护一个堆，先把买每一种商品用第一档优惠真正需要花的钱放堆里，然后拿出最小的，把对应的商品使用第二档优惠的花的钱放进去，以此类推，直到钱不够了。
//
// Created by zxc on 2020/9/23.
//
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
const int D=1e6+50;
int n,d;
int a[N],b[N];
bool cmp(int x,int y){
return x>y;
}
struct node{
int i,j,cos;
bool operator <(const node& rhs)const{
return cos>rhs.cos;
}
};
int main(){
// freopen("in.txt","r",stdin);
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
}
sort(a+1,a+1+n,cmp);
sort(b+1,b+1+n,cmp);
priority_queue<node> q;
for(int i=1;i<=n;i++){
q.push(node{i,1,a[i]-b[1]});
}
int ans=0;
int res=d;
while(!q.empty()){
node t=q.top();
q.pop();
res-=t.cos;
if(res<0){
res+=t.cos;
break;
}
ans++;
if(t.j+1<=n){
q.push(node{t.i,t.j+1,a[t.i]-b[t.j+1]});
}else{
// 考试时没写上这个，也过了
q.push(node{t.i,t.j+1,a[t.i]});
}
}
printf("%d %d
",ans,res);
}