D. Sum Graph
https://codeforces.com/contest/1816/problem/D 2000
题解：我们对于给定的n，1操作两次，分别为+ n，+ n-1。如此我们可以得到一个只有一条路径的图，端点分别为n和（n+1)/2，接下来思路就很明了了，以1为定点，n-1次2询问找到距离1最远的点u,再以u为端点遍历整个链，按距离排序后即可得到序列，总共由两种可能端点，故给出两个序列，且询问次数恰好为2n。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10;
int a[N],b[N];
pair<int,int> c[N];
void do1(int x){
cout<<"+ "<<x<<endl;
int k;cin>>k;
}
int do2(int x,int y){
cout<<"? "<<x<<" "<<y<<endl;
int k;cin>>k;
return k;
}
void solve(){
int n;cin>>n;
if(n==2){
cout<<"! 1 2 2 1"<<endl;
int k;cin>>k;
return;
}
do1(n+1);do1(n);
int cnt=0,p=0;
for(int i=2;i<=n;i++){
int w=do2(1,i);
if(w>cnt){
cnt=w;p=i;
}
}
int tt=0;
for(int i=1;i<=n;i++){
if(i==p) continue;
int w=do2(p,i);
c[++tt]={w,i};
}
int w=p;
sort(c+1,c+n-1+1);
a[w]=n;
b[w]=(n+1)/2;
int ok=-1,pre=n,e=n-1;
for(int i=2;i<=n;i++){
int u=c[i-1].first,v=c[i-1].second;
pre=pre+ok*e;
a[v]=pre;
e--;
ok=-ok;
}
ok=1,pre=(n+1)/2,e=1;
if(n%2) ok=-1;
for(int i=2;i<=n;i++){
int u=c[i-1].first,v=c[i-1].second;
pre=pre+ok*e;
b[v]=pre;
e++;
ok=-ok;
}
cout<<"! ";
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
for(int i=1;i<=n;i++) cout<<b[i]<<" ";
cout<<endl;
int ee;cin>>e;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--) solve();
}
E. Between
https://codeforces.com/contest/1816/problem/E 2200
题解：（感觉没D难）我们可以将(u,v)视为u向v连一条有向边，忽略所有以1为出发点的边，则若有限则必定要以u为“根”的一张有向图且包含所有节点，很显然若有点x例外则可以循环x到无限，若不包含1则可以按顺序拓扑遍历无数遍或按有一个无出边环一直走即可。现考虑有限情况，我们以1为根节点查找每个节点到1的最小距离d[i],按d由大到小排成一个序列，由于1只能出现一次，故d=1的点只能出现两次，d=k的点只能出现k+1次，我们不断循环这个序列每次去除不能继续循环的点即可达到最大值。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100100;
vector<int> g[N],f[N];
int a[N],d[N],c[N],v[N],in[N],out[N],vis[N];
queue<int> q,qq;
pair<int,int> e[N];
void bfs(int x,int faa){
vis[x]=1;d[x]=0;
qq.push(x);
while(qq.size()){
int u=qq.front();qq.pop();
for(auto it:f[u]){
if(vis[it]) continue;
vis[it]=1;
d[it]=min(d[it],d[u]+1);
qq.push(it);
}
}
}
void solve(){
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++){
g[i].clear();f[i].clear();d[i]=1e9,v[i]=0,in[i]=out[i]=vis[i]=0;
}
for(int i=1;i<=m;i++){
int u,vv;cin>>u>>vv;
if(u==1) continue;
g[u].push_back(vv);in[vv]++;out[u]++;
f[vv].push_back(u);
}
if(n==1){
cout<<"FINITE"<<endl;
cout<<1<<endl;
cout<<1<<endl;
return;
}
int w=0,t=0;
for(int i=2;i<=n;i++){
if(out[i]==0){
cout<<"INFINITE"<<endl;return;
}
}
if(in[1]==0){
cout<<"INFINITE"<<endl;return;
}
for(int i=2;i<=n;i++){
if(in[i]==0){
if(out[i]==0){
cout<<"INFINITE"<<endl;return;
}
else
q.push(i),t++;
}
}
// while(q.size()){
// int x=q.front();q.pop();
// for(auto it:g[x]){
// in[it]--;
// if(in[it]==0) q.push(it),t++;
// }
// }
// if(t<n){
// cout<<"INFINITE"<<endl;return;
// }
d[1]=0;bfs(1,0);
for(int i=1;i<=n;i++){
if(d[i]==1e9){
cout<<"INFINITE"<<endl;return;
}
v[d[i]]++;
e[i]={d[i],i};
}
sort(e+1,e+n+1);
int ans=1;
for(int i=1;i<=n;i++){
ans+=v[i]*(i+1);
}
cout<<"FINITE"<<endl;
cout<<ans<<endl;
w=1;
for(int i=n;i>=2;i--){
cout<<e[i].second<<" ";
}
cout<<"1 ";
for(int i=1;i<=e[n].first;i++){
for(int j=n;j>1;j--){
int x=e[j].first,y=e[j].second;
if(x<w) break;
cout<<y<<" ";
}
w++;
}
cout<<endl;
}
signed main(){
int T;cin>>T;
while(T--){
solve();
}
}
D. The Strongest Build
https://codeforces.com/problemset/problem/1574/D 2000
题解：感觉是一个STL学习题，，，
贪心地想，若答案是每行最大值，且其没被ban，则答案为它，否则答案是被ban的组合中某个的改变一个位置。我们遍历它每次二分查找是否被使用过即可。
#include<bits/stdc++.h>
//#define int long long
#define forn(i,n) for(int i=0;i<n;i++)
using namespace std;
const int N=100100;
vector<vector<int> > a,b;
void solve(){
int n;cin>>n;
a.resize(n);
forn(i,n){
int c;cin>>c;
a[i].resize(c);
forn(j,c) cin>>a[i][j];
}
int m;cin>>m;
b.resize(m);
forn(i,m){
b[i].resize(n);
forn(j,n){
cin>>b[i][j];
--b[i][j];
}
}
sort(b.begin(),b.end());
vector<int> ult(n);
forn(i,n) ult[i]=int(a[i].size())-1;
if(!binary_search(b.begin(),b.end(),ult)){
forn(i,n) cout<<ult[i]+1<<" ";
puts("");
return ;
}
int mx=0;
vector<int> ans(n);
forn(i,m){
vector<int> tmp=b[i];
int sum=0;
forn(j,n) sum+=a[j][tmp[j]];
forn(j,n) if(tmp[j]!=0){
--tmp[j];
if(!binary_search(b.begin(),b.end(),tmp)&&sum-a[j][tmp[j]+1]+a[j][tmp[j]]>mx){
mx=sum-a[j][tmp[j]+1]+a[j][tmp[j]];
ans=tmp;
}
++tmp[j];
}
}
forn(i,n){
cout<<ans[i]+1<<" ";
}
puts("");
}
signed main(){
// int T;cin>>T;
// while(T--)
solve();
}
Rain （great question ！）
https://codeforces.com/problemset/problem/1710/B 2100
题解：首先我们贪心地想可以发现只有在落雨中心位置可能成为最大值，其他位置总会比某个中心小，故我们只要满足每个中心<m即可。我们可以按照二阶差分得到所有雨下过之后每个位置的值（你问1e9咋差分？问的好！我们每次将差分左右端点（每次两个差分序列）放入数对数组中，排序后简单计算即可得到）。对于每个位置j如果其能够然位置aj<=m的i,则需满足pi-|xi-j|>=m-aj,我们拆分绝对值得到的一片二维空间的区域为两条k=-1,k=1的直线交线的上方，而对于每个j取并我们得到的最终区域仍然是一个V字区域，我们考虑每个(xi,pi)是否在其中即可得到答案。
#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=3e5+10;
vector<pair<int,int> > g;
map<int,int> w,s;
int x[N],p[N];
void solve(){
int n,m;cin>>n>>m;
w.clear(),g.clear(),s.clear();
for(int i=1;i<=n;i++){
cin>>x[i]>>p[i];
int l=x[i]-p[i]+1,r=x[i]+p[i]+1;
g.pb({l,1});
g.pb({x[i]+1,-2});
g.pb({x[i],0});
g.pb({r,1});
}
sort(g.begin(),g.end());
int pre=0,k=0,sum=0;
for(auto it:g){
int u=it.first,v=it.second;
sum+=v;
s[u]=sum;
// cout<<u<<" "<<s[u]<<endl;
}
w[g[0].first]=s[g[0].first];
for(int i=1;i<g.size();i++){
pair<int,int> it=g[i];
int u=it.first,v=it.second;
if(u==g[i-1].first) continue;
w[u]=w[g[i-1].first]+s[g[i-1].first]*(u-g[i-1].first-1)+s[u];
}
int xl=-1e18,xr=-1e18;
for(int i=1;i<=n;i++){
int ww=w[x[i]];
if(ww<=m) continue;
xl=max(xl,ww-m+x[i]);
xr=max(xr,ww-m-x[i]);
}
double mp=(xl-xr)*1.0/2.0;
for(int i=1;i<=n;i++){
double k=x[i];
int y;
if(k*1.0<mp){
y=-x[i]+xl;
}
else{
y=x[i]+xr;
}
if(y>p[i]){
cout<<0;
}
else cout<<1;
}
cout<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--)
solve();
}
D. The way home(不错的图论题） 2100
https://codeforces.com/problemset/problem/1801/D
题解：首先我们贪心地想，肯定是在某个w大的位置攒够足够多的钱后直奔n，但若想要到达这个点我们需要在先前某个比较大的点积攒够钱来到这个点，故我们可以考虑维护f(i,j)表示当前在i，经过的具有最大w的点为j时得到的{cout，remain}，cout需要优先考虑越小越好，remain其次考虑越大越好，因为cout小具有更好的灵活性，可以转化为最大能达到的remain。进一步思考发现求得每一个(i,j)点的数对最小，即为一种最短路，我们用dij维护即可。