A. Helpful Maths
题目大意
给一个连加计算式，只包含数字 1、2、3，要求重新排序，使得连加的数字从小到大
做法分析
把所有的数字记录下来，从小到大排序输出即可
参考代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm> using namespace std; const int N=; char buff[];
int A[], n; int main() {
scanf("%s", buff);
n=;
for(int i=; buff[i]; i+=) A[n++]=buff[i]-'';
sort(A, A+n);
printf("%d", A[]);
for(int i=; i<n; i++) printf("+%d", A[i]);
printf("\n");
return ;
}
A
B. Xenia and Ringroad
题目大意
昨晚眼睛盯着屏幕仔仔细细的看了四遍题意，硬是没看懂...下面是我猜的题意，不知道对不对，反正按照这个题意写的代码过了
有 n 个房子编号 1 到 n 按照顺时针围成一个圈，相邻两个房子之间的距离是 1，有 m 个任务编号 1 到 m，每个任务为 i 为到达相应的房子中去，问顺序的（从 1 号任务开始完成到 m 号任务）完成这些任务最少需要走多短的路程
做法分析
模拟题，直接模拟就行
参考代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm> using namespace std; typedef long long LL;
const int N=; int n, m;
LL A[N]; int main() {
scanf("%d%d", &n, &m);
for(int i=; i<=m; i++) {
scanf("%I64d", &A[i]);
A[i]--;
}
LL last=, ans=;
for(int i=; i<=m; i++) {
if(A[i]>=last) ans+=A[i]-last, last=A[i];
else ans+=n-last+A[i], last=A[i];
}
printf("%I64d\n", ans);
return ;
}
B
C. Xenia and Weights
题目大意
有 10 个重量分别为 1 到 10 的砝码可用，以及一个天平，现在往天平上添加砝码，添加的规则如下：
1. 第 i 次添加到左边的盘中，那么第 i+1 添加到右边的盘中
2. 第 i 次添加的砝码的重量不等于第 i+1 次添加的砝码的重量
3. 往一个盘中添加完砝码之后，要求这个盘中的所有砝码的重量严格大于另一个盘中砝码的重量
给你一些可用的砝码，以及添加砝码的次数 m(1 ≤ m ≤ 1000)，问是否存在这样一个砝码添加序列，存在子的话输出这个序列
做法分析
动态规划，定义状态：f[i][cur][mor] 表示第 i 次添加的砝码重量是 cur，添加完之后当前盘比另一盘重 mor 的状态是否可达，由于 m 最大为 1000，砝码重量最大为 10，所以状态的数量为 10^5，状态的转移为 10，时间复杂度为 10^6
初值：f[0][i][i]=1 表示第 0 次添加重量为 i 的砝码，添加完之后肯定比另一个空盘多 i，其他状态为 0
转移：f[i][cur][mor] 可以推出 f[i+1][nxt][nxt-mor]，这里要求 cur!=nxt 且 nxt-mor>0
终值：f[m-1][i][j] 只要有一个状态可达，序列存在，往回递归的找解，否则不存在
参考代码
#include <iostream>
#include <cstring>
#include <cstdio> using namespace std; const int N=; bool f[N][][];
char buff[];
int n; void PRINT(int dep, int cho, int mor) {
int pre=-;
for(int i=; i<= && pre==-; i++)
if(f[dep-][i][cho-mor] && i!=cho) pre=i;
if(dep==) printf("%d", pre);
else PRINT(dep-, pre, cho-mor);
printf(" %d", cho);
} int main() {
scanf("%s%d", buff, &n);
memset(f, , sizeof f);
for(int i=; i<=; i++) if(buff[i-]=='') f[][i][i]=;
for(int i=; i<n; i++) {
for(int j=; j<=; j++) {
for(int k=; k<=; k++) {
if(!f[i][j][k]) continue;
for(int nxt=; nxt<=; nxt++) {
if(buff[nxt-]!='') continue;
if(nxt-k<=) continue;
if(nxt==j) continue;
f[i+][nxt][nxt-k]=;
}
}
}
}
int id1=-, id2=-;
for(int i=; i<= && id1==-; i++)
for(int j=; j<= && id1==-; j++) {
if(f[n-][i][j]) {
id1=i, id2=j;
break;
}
}
if(id1==-) {
printf("NO\n");
return ;
}
printf("YES\n");
if(n==) printf("%d\n", id1);
else PRINT(n-, id1, id2), printf("\n");
return ;
}
C
D. Xenia and Bit Operations
题目大意
给一个长度为 2^n 的数组，现在有 n 个操作，把这个数组变成一个数：
1. 如果 i%2==1 那么，把第 1 个和第 2 个按位取或得到新数，把第 3 个和第 4 个按位取或得到新数...
2. 如果 i%2==0 那么，把第 1 个和第 2 个按位异或得到新数，把第 3 个和第 4 个按位异或得到新数...
现在给了 m 个询问，每个询问先把第 p 个位置的值改为 q，然后输出按照上面操作得到的数
数据规模：1 ≤ n ≤ 17, 1 ≤ m ≤ 105
做法分析
典型的线段树水题，每个节点保存如下信息
1. s t 这个节点表示的区间
2. val 这个节点表示的区间按照要求的操作所得到的数
3. dep 这个节点的层号
每次 pushup 的时候根据层号 pushup：
1. 层号为奇数 fa.val=L.val 按位或 R.val
2. 层号为偶数 fa.val=L.val 按位异或 R.val
线段树有 3 个函数：
1. build 建树
2. update 将某个位置的值修改
3. pushup 由儿子节点的 val 计算父亲节点的 val
参考代码
#include <iostream>
#include <cstring>
#include <cstdio> using namespace std; const int N=; int n, m, A[N]; struct Segment_Tree {
struct Node {
int s, t, dep, val;
void init(int L, int R, int a) {
s=L, t=R, dep=a, val=A[L];
}
} T[N<<]; void pushUp(Node &fa, Node &L, Node &R) {
if(fa.dep&) fa.val=L.val|R.val;
else fa.val=L.val^R.val;
} void build(int id, int dep, int L, int R) {
T[id].init(L, R, dep);
if(L==R) return;
int mid=(L+R)>>;
build(id<<, dep-, L, mid);
build(id<<|, dep-, mid+, R);
pushUp(T[id], T[id<<], T[id<<|]);
} void update(int id, int pos, int val) {
if(T[id].s==T[id].t) {
T[id].val=val;
return;
}
int mid=(T[id].s+T[id].t)>>;
if(pos<=mid) update(id<<, pos, val);
else update(id<<|, pos, val);
pushUp(T[id], T[id<<], T[id<<|]);
}
} tree; int main() {
// freopen("in", "r", stdin);
scanf("%d%d", &n, &m);
int old=n;
n=(<<n);
for(int i=; i<=n; i++) scanf("%d", &A[i]);
tree.build(, old, , n);
for(int i=, p, q; i<m; i++) {
scanf("%d%d", &p, &q);
tree.update(, p, q);
printf("%d\n", tree.T[].val);
}
return ;
}
D
E. Three Swaps
题目大意
给一个序列，初始时为：1、2、3、4、...、n
现在每次操作翻转一个区间的所有数，最多翻转三次，会得到一个新的序列
现在给你新的那个序列，要求你给出一个合法的翻转操作指令，使得从最初的序列变成给你的序列
题目保证存在解，且最多不超过 3 次翻转
做法分析
考虑从当前的序列翻回去
假设 [1, L-1]， [R+1, n] 这两个区间是排好序的，即：A[i]=i，对于 i 属于这两个区间
[L, R] 这个区间是乱序的，即 A[L]!=L 且 A[R]!=R
另 A[Lpos]=L，A[Rpos]=R
那么，每次翻转的时候，有两种选择：
1. 翻转 [L, Lpos]
2. 翻转 [Rpos, R]
这样做必然能够将序列翻转回去，直接 DFS 即可，最后输出解的时候需要注意：人家问的是怎么翻转到当前的序列哦，好多人的答案反了...
当时猜了个结论就写了，早上醒来想了想证明，挺麻烦的，懒得写了，好饿啊...
参考代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm> using namespace std; const int N=; struct node {
int s, t;
void init(int a, int b) {
s=a, t=b;
}
} ans[];
int A[][N], n; int checkL(int dep) {
if(A[dep][]!=) return ;
for(int i=; i<=n; i++) if(A[dep][i]!=A[dep][i-]+) return i;
return -;
} int checkR(int dep) {
if(A[dep][n]!=n) return n;
for(int i=n-; i>=; i--) if(A[dep][i]!=A[dep][i+]-) return i;
return -;
} int findpos(int dep, int val) {
for(int i=; i<=n; i++) if(A[dep][i]==val) return i;
} bool DFS(int dep) {
if(dep==) if(checkL(dep)!=-) return false;
else {
printf("%d\n", dep);
for(int i=dep-; i>=; i--) printf("%d %d\n", ans[i].s, ans[i].t);
return true;
} int L=checkL(dep), R=checkR(dep);
if(L==- || R==-) {
printf("%d\n", dep);
for(int i=dep-; i>=; i--) printf("%d %d\n", ans[i].s, ans[i].t);
return true;
}
for(int i=; i<=n; i++) A[dep+][i]=A[dep][i];
int Lpos=findpos(dep+, L), Rpos=findpos(dep+, R); reverse(A[dep+]+L, A[dep+]+Lpos+);
ans[dep].init(L, Lpos);
if(DFS(dep+)) return true;
reverse(A[dep+]+L, A[dep+]+Lpos+); ans[dep].init(Rpos, R);
reverse(A[dep+]+Rpos, A[dep+]+R+);
if(DFS(dep+)) return true;
reverse(A[dep+]+Rpos, A[dep+]+R+); return false;
} int main() {
scanf("%d", &n);
for(int i=; i<=n; i++) scanf("%d", &A[][i]);
DFS();
return ;
}
E
这场比赛总算圆了我 div2 AK 一场的梦，爽，不过，题目的质量确实不怎么样...