DAY1
转圈游戏
列出式子(x+km)%n，快速幂。
// codevs3285
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 1e18
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; LL power(LL a,LL b,LL c) {
LL res=1;
while (b) {
if (b&1) res=res*a%c;
b>>=1;a=a*a%c;
}
return res;
}
int main() {
LL n,m,k,x;
scanf("%lld%lld%lld%lld",&n,&m,&k,&x);
printf("%lld",(m*power(10,k,n)%n+x)%n);
return 0;
}
火柴排队
刚刚看了题目我整个人就慌了。。尼玛怎么感觉跟快排有点关系，快排我百八年前就忘记怎么打了。。C++选手沉迷sort，日渐消瘦→_→。稍加分析，其实不过是个离散化逆序对。。
// codevs3286
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define MOD 99999997
#define inf 1e18
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=100010;
int a[maxn],b[maxn],ta[maxn],tb[maxn],c[maxn],pos[maxn],n; int lowbit(int x) {return x&-x;}
int query(int x) {
int s=0;
for (int i=x;i;i-=lowbit(i)) s=(s+c[i])%MOD;
return s;
}
void add(int x) {
for (int i=x;i<=n;i+=lowbit(i)) c[i]=(c[i]+1)%MOD;
}
int main() {
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]),ta[i]=a[i];
for (int i=1;i<=n;i++) scanf("%d",&b[i]),tb[i]=b[i];
sort(ta+1,ta+1+n);
sort(tb+1,tb+1+n);
for (int i=1;i<=n;i++) a[i]=lower_bound(ta+1,ta+1+n,a[i])-ta;
for (int i=1;i<=n;i++) b[i]=lower_bound(tb+1,tb+1+n,b[i])-tb;
for (int i=1;i<=n;i++) pos[a[i]]=i;
for (int i=1;i<=n;i++) b[i]=pos[b[i]];
int ans=0;
for (int i=n;i;i--) {
ans=(ans+query(b[i]))%MOD;
add(b[i]);
}
printf("%d",ans);
return 0;
}
货车运输
很显然，答案一定在图的最大生成树上。所以我们构出最大生成树，那么问题就转化为了在树上询问两点间的最小边权，一开始还想无脑树链剖分，然而不想打太长的代码。。那就倍增吧。
// codevs3287
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define MOD 99999997
#define inf 2147483647
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=100010,maxm=500010;
struct edge {int to,next,w;}e[maxn<<1];
struct data {int u,v,w;}c[maxm];
int head[maxn],f[maxn],fa[maxn][30],d[maxn][30],bin[30],deep[maxn],vis[maxn];
int n,m,cnt; bool cmp(data a,data b) {
return a.w>b.w;
}
void link(int u,int v,int w) {
e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].w=w;
e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;e[cnt].w=w;
}
int find(int x) {
return f[x]==x ? x : f[x]=find(f[x]);
}
void dfs(int x) {
vis[x]=1;
for (int i=1;i<=20;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for (int i=1;i<=20;i++) d[x][i]=min(d[x][i-1],d[fa[x][i-1]][i-1]);
for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa[x][0]) {
deep[e[i].to]=deep[x]+1;
fa[e[i].to][0]=x;
d[e[i].to][0]=e[i].w;
dfs(e[i].to);
}
}
int lca(int x,int y) {
if (deep[x]<deep[y]) swap(x,y);
int t=deep[x]-deep[y],dx=inf,dy=inf;
for (int i=0;bin[i]<=t;i++) if (t&bin[i]) {
dx=min(dx,d[x][i]);x=fa[x][i];
}
for (int i=20;i>=0;i--) if (fa[x][i]!=fa[y][i]) {
dx=min(d[x][i],dx);dy=min(d[y][i],dy);
x=fa[x][i],y=fa[y][i];
}
return x==y ? min(dx,dy) : min(min(d[x][0],dx),min(d[y][0],dy));
}
int main() {
bin[0]=1;for (int i=1;i<=20;i++) bin[i]=bin[i-1]<<1;
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++) scanf("%d%d%d",&c[i].u,&c[i].v,&c[i].w);
sort(c+1,c+1+m,cmp);
for (int i=1;i<=n;i++) f[i]=i;
for (int i=1;i<=m;i++) {
int r1=find(c[i].u),r2=find(c[i].v);
if (r1!=r2) {
f[r1]=r2;
link(c[i].u,c[i].v,c[i].w);
}
}
for (int i=1;i<=n;i++) if (!vis[i]) dfs(i);
int q;scanf("%d",&q);
for (int x,y,i=1;i<=q;i++) {
scanf("%d%d",&x,&y);
if (find(x)!=find(y)) puts("-1");
else printf("%d\n",lca(x,y));
}
return 0;
}
DAY2
积木大赛
还以为要分治，稍加分析，发现就是个sb题。。
// codevs3288
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define MOD 99999997
#define inf 2147483647
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=100010;
int a[maxn],n; int main() {
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
int ans=0;
for (int i=1;i<=n;i++) ans+=max(0,a[i]-a[i-1]);
printf("%d",ans);
return 0;
}
花匠
很容易列出1d/1d的dp方程，然后这是个很经典的二维偏序问题，用树状数组做。h的值域是从0开始的，所以开始的时候要把他们全部加上1，Re了一发。。。要是联赛就完蛋了。。
UPD：看了题解的我眼泪掉下来，尼玛怎么这么短，好像还是模拟。。。
// codevs3289
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define MOD 99999997
#define inf 2000000000
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=1000010;
int a[maxn],f[maxn][2],g[maxn][2],n,m;
int c0[maxn],c1[maxn],d0[maxn],d1[maxn]; int lowbit(int x) {return x&-x;}
int query(int *c,int x) {
int s=0;
for (int i=x;i;i-=lowbit(i)) s=max(s,c[i]);
return s;
}
void add(int *c,int x,int val) {
for (int i=x;i<=m;i+=lowbit(i)) c[i]=max(c[i],val);
}
int main() {
scanf("%d",&n);
m=0;
for (int i=1;i<=n;i++) {scanf("%d",&a[i]);a[i]++;m=max(m,a[i]);}
for (int i=1;i<=n;i++) {
f[i][0]=query(c1,a[i]-1);
g[i][1]=query(d0,a[i]-1)+1;
f[i][1]=query(c0,m-a[i])+1;
g[i][0]=query(d1,m-a[i]);
add(c0,m-a[i]+1,f[i][0]);add(c1,a[i],f[i][1]+1);
add(d0,a[i],g[i][0]);add(d1,m-a[i]+1,g[i][1]+1);
}
int ans=0;
for (int i=1;i<=n;i++)
ans=max(ans,max(max(f[i][0],f[i][1]),max(g[i][0],g[i][1])));
printf("%d",ans);
return 0;
}
华容道
脑袋好痛。。。
UPD：终于切了mdzz（2016.11.7），网上题解很多，看了后才会的。。先处理出一个${move[x][y][i][j]}$数组，表示对于格子${（x,y）}$，它想要走到相邻${i}$方向的格子上去，空格在它相邻的${j}$位置。注意，这里想要到达的格子以及空格只局限于四周4格格子。可以发现，这个数组我们可以很轻松的通过BFS预处理出来。然后设计最短路状态：${dis[x][y][s]}$表示对于格子${（x,y）}$，空格在它相邻${s}$方向，从初始状态到达此状态的最小步数。然后转移的话就很显然，当前格子可以与空格交换位置。于是SPFA出解，注意特判起点与终点相同的情况。
// codevs3290
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
#define inf 1000000000
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; struct data {int x,y,s;};
int move[31][31][4][4],dis[31][31][4],mark[31][31],vis[31][31][4],a[31][31];
int xx[4]={-1,1,0,0},yy[4]={0,0,-1,1};
int n,m,Q; int bfs(int sx,int sy,int ex,int ey) {
if (!a[sx][sy] || !a[ex][ey]) return inf;
if (sx==ex && sy==ey) return 0;
memset(mark,0,sizeof(mark));
queue<data> q;
q.push((data){sx,sy,0});mark[sx][sy]=1;
while (!q.empty()) {
data now=q.front();q.pop();
for (int i=0;i<4;i++) {
int x=now.x+xx[i],y=now.y+yy[i];
if (!a[x][y] || mark[x][y]) continue;
mark[x][y]=1;
if (x==ex && y==ey) return now.s+1;
q.push((data){x,y,now.s+1});
}
}
return inf;
}
void calmove() {
register int i;
for (i=1;i<=n;i++)
for (int j=1;j<=m;j++)
for (int k=0;k<4;k++)
for (int l=0;l<4;l++) move[i][j][k][l]=inf;
for (i=1;i<=n;i++)
for (int j=1;j<=m;j++) if (a[i][j]) {
a[i][j]=0;
for (int k=0;k<4;k++) {
if (!a[i+xx[k]][j+yy[k]]) continue;
for (int l=0;l<4;l++)
if (a[i+xx[l]][j+yy[l]]) {
if (l<k) {move[i][j][k][l]=move[i][j][l][k];continue;}
move[i][j][k][l]=bfs(i+xx[l],j+yy[l],i+xx[k],j+yy[k])+1;
//printf("%d %d %d %d : %d\n",i,j,k,l,move[i][j][k][l]);
}
}
a[i][j]=1;
}
}
void SPFA(int ex,int ey,int sx,int sy,int tx,int ty) {
queue<data> q;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
for (int k=0;k<4;k++) dis[i][j][k]=inf,vis[i][j][k]=0;
a[sx][sy]=0;
for (int i=0;i<4;i++) if (a[sx+xx[i]][sy+yy[i]]) {
dis[sx][sy][i]=bfs(ex,ey,sx+xx[i],sy+yy[i]);
q.push((data){sx,sy,i});
}
a[sx][sy]=1;
while (!q.empty()) {
data now=q.front();q.pop();
vis[now.x][now.y][now.s]=0;
for (int i=0;i<4;i++) {
int x=now.x+xx[i];
int y=now.y+yy[i];
int s=i^1;
if (!a[x][y]) continue;
if (a[x][y] && dis[now.x][now.y][now.s]+move[now.x][now.y][now.s][i]<dis[x][y][s]) {
dis[x][y][s]=dis[now.x][now.y][now.s]+move[now.x][now.y][now.s][i];
if (!vis[x][y][s]) q.push((data){x,y,s}),vis[x][y][s]=1;
}
}
}
int ans=min(min(dis[tx][ty][0],dis[tx][ty][1]),min(dis[tx][ty][2],dis[tx][ty][3]));
if (ans<inf) printf("%d\n",ans);
else puts("-1");
}
int main() {
scanf("%d%d%d",&n,&m,&Q);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) scanf("%d",&a[i][j]);
calmove();
for (int ex,ey,sx,sy,tx,ty,i=1;i<=Q;i++) {
scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
if(!a[ex][ey] || !a[sx][sy] || !a[tx][ty]) puts("-1");
else if (sx==tx && sy==ty) puts("0");
else SPFA(ex,ey,sx,sy,tx,ty);
}
return 0;
}