Round 236 div.1
A：只需要每个点连接所有比他大的点，知道边用完为止。
//By BLADEVIL
#include <cmath>
#include <cstdio>
#define maxn 25; using namespace std; int main() {
int task; scanf("%d",&task);
while (task--) {
int n,p; scanf("%d%d",&n,&p);
int rest(*n+p);
for (int i=;(i<=n)&&rest;i++)
for (int j=i+;(j<=n)&&rest;j++) printf("%d %d\n",i,j),rest--;
}
return ;
}
B：求出g[i]=gcd(a[1],a[2]....a[i])，那么只需要从后向前贪心的考虑每个g[i]能不能被除掉就好了。
//By BLADEVIL
#include <cstdio>
#include <algorithm>
#define maxn 5010 using namespace std; int n,m;
int a[maxn],b[maxn],g[maxn]; int calc(int x) {
int ans();
for (int i=;i<=m;i++) while (!(x%b[i])) ans--,x/=b[i];
for (int i=;i*i<=x;i++) while (!(x%i)) ans++,x/=i;
if (x>) ans++;
return ans;
} int main() {
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++) scanf("%d",&a[i]),g[i]=__gcd(g[i-],a[i]);
for (int i=;i<=m;i++) scanf("%d",&b[i]);
int cur();
for (int i=n;i;i--) {
a[i]/=cur; g[i]/=cur;
if (calc(g[i])<) cur*=g[i],a[i]/=g[i];
}
//for (int i=1;i<=n;i++) printf("%d ",a[i]); printf("\n");
int ans();
for (int i=;i<=n;i++) ans+=calc(a[i]);
printf("%d\n",ans);
return ;
}
Round 238 div.1
A：我们发现其实最后的答案只与a[i][i]有关，那么我们只记录a[i]=a[i][i]，根据操作模拟就可以了。
//By BLADEVIL
#include <cstdio>
#define maxn 1010 using namespace std; int n;
int mat[maxn][maxn],a[maxn]; int main() {
//freopen("data.txt","r",stdin);
scanf("%d",&n);
for (int i=;i<=n;i++)
for (int j=;j<=n;j++) scanf("%d",&mat[i][j]);
for (int i=;i<=n;i++) a[i]=mat[i][i];
int ans();
for (int i=;i<=n;i++) ans=(ans+a[i])%;
int task; scanf("%d",&task);
while (task--) {
int x,y; scanf("%d",&x);
if (x==) printf("%d",ans); else {
scanf("%d",&x); ans^=;
}
}
printf("\n");
return ;
}
B：我们可以将每个给定的a[i]-1，查询s-a[i]+1位置是否被占用，被占用我们cnt++，表示和为s-1的数对加一，否则直接输出s-a[i]+1，然后再找出cnt个和为s-1的数对输出。
//By BLADEVIL
#include <cstdio>
#define maxn 1000010
#define s 1000000 using namespace std; int n,tot;
int flag[maxn]; int main() {
scanf("%d",&n);
for (int i=;i<=n;i++) {
int x; scanf("%d",&x);
flag[x]=; if (flag[s+-x]) tot++;
}
printf("%d\n",n);
for (int i=;i<=s;i++) {
if (tot&&!flag[i]&&!flag[s-i+]) {
tot--;
flag[i]=flag[s-i+]=;
printf("%d %d ",i,s-i+);
}
if (flag[i]&&!flag[s-i+]) printf("%d ",s-i+);
}
printf("\n");
return ;
}
C：深搜，同时每个点记录这个点剩下的一条没有被选定的边，枚举这个点的所有儿子，如果儿子的没有被选定的边不为0我们就画连接儿子的边和儿子剩下的边，否则判断这个点是否有剩下的边，有的话输出连接儿子的边和剩下的边，最后返回剩下的边。
//By BLADEVIL
#include <cstdio>
#define maxn 100010
#define maxm 200010 using namespace std; int n,m,l;
int pre[maxm],other[maxm],last[maxn];
int flag[maxn]; void connect(int x,int y) {
pre[++l]=last[x];
last[x]=l;
other[l]=y;
} int dfs(int x,int fa) {
flag[x]=; int cur();
for (int p=last[x];p;p=pre[p]) {
if (other[p]==fa) continue;
if (flag[other[p]]==) continue;
int edge;
if (!flag[other[p]]) edge=dfs(other[p],x); else edge=;
//printf("|%d %d\n",x,edge);
if (edge) printf("%d %d %d\n",x,other[p],edge); else
if (cur) printf("%d %d %d\n",cur,x,other[p]),cur=; else cur=other[p];
}
flag[x]=;
//printf("%d %d\n",x,cur);
return cur;
} int main() {
scanf("%d%d",&n,&m);
for (int i=;i<=m;i++) {
int x,y; scanf("%d%d",&x,&y);
connect(x,y); connect(y,x);
}
if (m&) printf("No solution\n\n"); else dfs(,-);
return ;
}
D：我们将每条线段能看到的最右面的线段设为这个线段的父亲，那么一个询问的答案就是这两个点的lca，对于父亲我们可以维护一个下凸壳来计算。
//By BLADEVIL
#include <cstdio>
#include <iostream>
#include <algorithm>
#define maxn 200010
#define LL long long using namespace std; struct rec {
LL x,y;
}a[maxn]; int n,t,l;
int q[maxn],jump[maxn][];
int pre[maxn],other[maxn],last[maxn],dep[maxn]; void connect(int x,int y) {
pre[++l]=last[x];
last[x]=l;
other[l]=y;
} int lca(int x,int y) {
if (dep[x]>dep[y]) swap(x,y);
int det(dep[y]-dep[x]);
for (int j=;j<=;j++) if (det&(<<j)) y=jump[y][j];
//printf("%d %d\n",x,y);
if (x==y) return x;
for (int j=;j>=;j--)
if (jump[x][j]!=jump[y][j]) x=jump[x][j],y=jump[y][j];
return jump[x][];
} void dfs(int x) {
for (int p=last[x];p;p=pre[p]) {
dep[other[p]]=dep[x]+;
dfs(other[p]);
}
} int main() {
cin>>n;
for (int i=;i<=n;i++) cin>>a[i].x>>a[i].y;
for (int i=n;i;i--) {
//for (int j=1;j<=t;j++) printf("%d ",q[j]); printf("\n");
while (t>&&(a[q[t]].y-a[q[t-]].y)*(a[i].x-a[q[t-]].x)>(a[q[t]].x-a[q[t-]].x)*(a[i].y-a[q[t-]].y)) t--;
jump[i][]=q[t];
q[++t]=i;
}
//for (int i=1;i<=n;i++) printf("%d ",jump[i][0]);
for (int i=;i<=n;i++) connect(jump[i][],i);
dfs();
//for (int i=1;i<=n;i++) printf("%d ",dep[i]); printf("\n");
for (int j=;j<=;j++)
for (int i=;i<=n;i++) jump[i][j]=jump[jump[i][j-]][j-];
int task; cin>>task;
while (task--) {
int x,y; cin>>x>>y;
cout<<lca(x,y)<<' ';
}
cout<<endl;
return ;
}
Round 240 div.1
A：假设n为偶数，奇数时最后一位随意，那么我们最后两个数为k-(n+2)/2和2*(k-(n+2)/2)，前n-2个数为不和最后两位相同的连续的数就可以了。
//By BLADEVIL
#include <cstdio>
#define maxn 100010 using namespace std; int n,k;
int a[maxn]; int main() {
scanf("%d%d",&n,&k);
if ((n==)&&(k)) {
printf("-1\n");
return ;
}
if (n-(n&)>*k) {
printf("-1\n");
return ;
}
int cur((n--(n&))/);
k-=cur;
a[n]=+k;
for (int i=,j=;i<=n--(n&);i+=) {
if (j==k) j+=;
if (j+==k) j+=;
if (j==(k<<)) j+=;
if (j+==(k<<)) j+=;
a[i]=j++; a[i+]=j++;
}
a[n-(n&)]=k,a[n--(n&)]=k<<;
for (int i=;i<=n;i++) printf(i==n?"%d\n":"%d ",a[i]);
return ;
}
B：设w[i][j]为第i位为j的方案数，然后转移就可以了。
//By BLADEVIL
#include <cmath>
#include <cstdio>
#define maxn 2010
#define d39 1000000007 using namespace std; int n,k;
int w[maxn][maxn]; int main() {
scanf("%d%d",&n,&k);
for (int i=;i<=n;i++) w[][i]=;
for (int i=;i<=k;i++)
for (int j=;j<=n;j++)
for (int g=;g<=sqrt(j);g++) if (!(j%g)) {
w[i][j]=(w[i][j]+w[i-][g])%d39;
if (g*g!=j) w[i][j]=(w[i][j]+w[i-][j/g])%d39;
}
int ans();
for (int i=;i<=n;i++) ans=(ans+w[k][i])%d39;
printf("%d\n",ans);
return ;
}
C：我们可以将一次翻转看成将左右儿子翻转然后交换左右儿子，我们可以发现每个块内的翻转对块与块之间的答案没有影响，那么我们只需要按照归并的过程求出长度为2^j的块与块合并的时候产生的答案，和交换块产生的答案，那么每次翻转我们就可以看做将j之前的所有当前状态取反，计算代价即可。
//By BLADEVIL
#include <cstdio>
#include <cstring>
#include <iostream>
#define maxn (1<<20)+100
#define LL long long using namespace std; LL n,len;
LL a[maxn],b[maxn];
LL w[][],flag[]; void work(LL p,LL cur) {
if (p>n) return ;
for (LL i=;i<=len;i+=cur) {
LL k1(i),k2(i+(cur>>)),det();
while ((k1<i+(cur>>))||(k2<i+cur)) {
if ((k1==i+(cur>>))||((a[k2]<a[k1])&&(k2<i+cur))) {
w[p][]+=i+(cur>>)-k1;
b[i+det]=a[k2];
k2++;
} else {
b[i+det]=a[k1];
k1++;
}
det++;
}
k1=i+(cur>>); k2=i;
while ((k1<i+cur)||(k2<i+(cur>>))) {
if ((k1==i+cur)||((a[k2]<a[k1])&&(k2<i+(cur>>)))) {
w[p][]+=i+cur-k1;
k2++;
} else k1++;
}
}
memcpy(a,b,sizeof b);
work(p+,cur<<);
} int main() {
cin>>n; len=;
for (LL i=;i<=n;i++) len*=;
for (LL i=;i<=len;i++) cin>>a[i];
work(,);
LL ans();
for (LL i=;i<=n;i++) ans+=w[i][];
//for (LL i=1;i<=n;i++) printf("%d ",w[i][0]); printf("\n");
//for (LL i=1;i<=n;i++) printf("%d ",w[i][1]); printf("\n");
for (LL i=;i<=n;i++) flag[i]=;
//printf("%d\n",ans);
LL task; cin>>task;
while (task--) {
LL x; cin>>x;
for (LL i=;i<=x;i++) ans+=w[i][flag[i]]-w[i][flag[i]^];
for (LL i=;i<=x;i++) flag[i]^=;
cout<<ans<<endl;
}
return ;
}
Round 245 div.1
A：tree-dp，设w[i][0..1]表示这个节点的状态和最后的相同（1），不相同（0），且每两层的儿子节点都符合这个状态的最小代价，然后转移就可以了，其实这道题相当于两棵互不影响的树，分别做tree-dp。
//By BLADEVIL
#include <cstdio>
#define maxn 100010
#define maxm 200020 using namespace std; int n,l;
int a[maxn],b[maxn];
int other[maxm],last[maxn],pre[maxm];
int que[maxn],dep[maxn];
int w[maxn][]; void connect(int x,int y) {
pre[++l]=last[x];
last[x]=l;
other[l]=y;
} void dfs(int x,int cur) {
if (a[x]^b[x]^(!cur)) printf("%d\n",x),cur^=;
for (int p=last[x];p;p=pre[p]) if (dep[other[p]]>dep[x])
for (int q=last[other[p]];q;q=pre[q]) if (dep[other[q]]>dep[other[p]])
dfs(other[q],cur);
} int main() {
scanf("%d",&n);
for (int i=;i<n;i++) {
int x,y; scanf("%d%d",&x,&y);
connect(x,y); connect(y,x);
}
for (int i=;i<=n;i++) scanf("%d",&a[i]);
for (int i=;i<=n;i++) scanf("%d",&b[i]);
int h(),t();
que[]=; dep[]=;
while (h<t) {
int cur=que[++h];
for (int p=last[cur];p;p=pre[p]) {
if (dep[other[p]]) continue;
que[++t]=other[p]; dep[other[p]]=dep[cur]+;
}
}
for (int i=n;i;i--) {
int x=que[i];
for (int p=last[x];p;p=pre[p]) {
if (dep[other[p]]<dep[x]) continue;
//w[x][0]+=w[other[p]][1]; w[x][1]+=w[other[p]][1];
for (int q=last[other[p]];q;q=pre[q]) {
if (dep[other[q]]<dep[other[p]]) continue;
if (a[x]^b[x]) w[x][]+=w[other[q]][]; else w[x][]+=w[other[q]][];
if (a[x]^b[x]) w[x][]+=w[other[q]][]; else w[x][]+=w[other[q]][];
}
}
if (a[x]^b[x]) w[x][]++; else w[x][]++;
}
//for (int i=1;i<=n;i++) printf("%d %d\n",w[i][0],w[i][1]);
int ans(w[][]);
for (int p=last[];p;p=pre[p]) ans+=w[other[p]][];
printf("%d\n",ans);
dfs(,);
for (int p=last[];p;p=pre[p]) dfs(other[p],);
return ;
}
B：记录w[i][j][1..4]表示四个方向到i,j点的最大值，然后枚举相遇的节点就可以了。
//By BLADEVIL
#include <cstdio>
#include <iostream>
#include <algorithm>
#define maxn 1010
#define LL long long using namespace std; LL n,m;
LL a[maxn][maxn];
LL w[][maxn][maxn]; void prepare() {
for (LL i=;i<=n;i++)
for (LL j=;j<=m;j++) w[][i][j]=max(w[][i][j-],w[][i-][j])+a[i][j];
for (LL i=;i<=n;i++)
for (LL j=m;j;j--) w[][i][j]=max(w[][i][j+],w[][i-][j])+a[i][j];
for (LL i=n;i;i--)
for (LL j=;j<=m;j++) w[][i][j]=max(w[][i+][j],w[][i][j-])+a[i][j];
for (LL i=n;i;i--)
for (LL j=m;j;j--) w[][i][j]=max(w[][i+][j],w[][i][j+])+a[i][j];
} int main() {
cin>>n>>m;
for (LL i=;i<=n;i++)
for (LL j=;j<=m;j++) cin>>a[i][j];
prepare();
LL ans();
for (LL i=;i<n;i++)
for (LL j=;j<m;j++)
ans=max(ans,w[][i-][j]+w[][i+][j]+w[][i][j+]+w[][i][j-]),
ans=max(ans,w[][i][j-]+w[][i][j+]+w[][i-][j]+w[][i+][j]);
cout<<ans<<endl;
return ;
}
C：深搜就可以了，有一种贪心不正确但是数据弱可以过去。
#include <cstdio>
#include <iostream>
#include <algorithm>
#define maxn 30 using namespace std; int n;
int w[maxn],p[maxn]; int dfs(int x,int used) {
//printf("%d %d\n",x,used);
if (x>n) return *max_element(p+,p++n)==;
for (int i=;i<=x;i++)
if ((p[i]>w[x]||p[i]==w[x]&&p[i]!=w[i]-)&&((used&(<<p[i])))==) {
p[i]-=w[x];
if (dfs(x+,x+<=n&&w[x]==w[x+]?used:)) return ;
p[i]+=w[x];
used|=<<p[i];
}
return ;
} int main() {
scanf("%d",&n);
for (int i=;i<=n;i++) scanf("%d",&w[i]);
sort(w+,w++n,greater<int>());
for (int i=;i<=n;i++) p[i]=w[i]-;
printf(dfs(,)?"YES\n":"NO\n");
}