A. Coder
题意：给出一个n*n的grid 现在要在上面尽量多的放棋子，问最多能放多少个，满足不存在任意两个棋子相邻。
分析：n是奇数：能放n*n/2
n是偶数：能放(n*n+1)/2
/**************************************** * File Name: 225a.cpp * Author: sky0917 * Created Time: 2014年01月20日 23:28:39 ****************************************/ #include <map> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 1000005; int a[maxn]; int main(){ int n; while (scanf("%d",&n)!=EOF){ if (n % 2 == 0){ printf("%d\n",n*n/2); int cnt = 0; for (int i=0; i<n; i++){ cnt++; for (int j=0; j<n; j++){ if ((j+cnt)%2==0){ putchar(‘C‘); } else putchar(‘.‘); } puts(""); } } else{ printf("%d\n",(n*n+1)/2); int cnt = 0; for (int i=0; i<n; i++){ for (int j=0; j<n; j++){ if ((j+cnt)%2==0){ putchar(‘C‘); } else putchar(‘.‘); } cnt++; puts(""); } } } return 0; }
B. Multitasking
题意：有n个数组，每个数组有m个数，现在最多能进行m*(m-1)/2次操作，每次给出i,j，如果然后每个数组中如果
a[i] < a[j] 则交换之，否则不交换，输出操作序列，和次数。
分析：直接模拟。
/**************************************** * File Name: 225b.cpp * Author: sky0917 * Created Time: 2014年01月20日 23:48:05 ****************************************/ #include <map> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 102; int g[maxn][maxn]; int r[maxn]; struct node{ int ll, rr; }q[maxn * maxn]; int main(){ int n, m, k; while (scanf("%d %d %d",&n,&m,&k)!=EOF){ int a, b; for (int i=0; i<n; i++){ for (int j=0; j<m; j++){ scanf("%d",&r[j]); } for (int j=0; j<m; j++){ for (int l=j+1; l<m; l++){ if (k == 0 && r[j] > r[l]){ g[j][l] = 1; } if (k == 1 && r[j] < r[l]){ g[l][j] = 1; } } } } int tp = 0; for (int i=0; i<m; i++){ for (int j=0; j<m; j++){ if (g[i][j]){ q[tp].ll = i; q[tp++].rr = j; } } } printf("%d\n",tp); for (int i=0; i<tp; i++){ printf("%d %d\n",q[i].ll+1,q[i].rr+1); } } return 0; }
C. Milking cows
题意：有n头牛，他们要么向左看，要么向右看，现在要给每个牛挤一次奶，被挤奶的牛的两侧，所有看到它的牛的产奶量
都会减去 1，现在要找到一个挤奶序列，使得总的减少的奶最少，被挤奶的奶牛不会在减少奶。
分析：可以按照能看到别的牛的数量从小到大一次把牛加进来，相当于是把过程倒过来。
还看到一种思路：从左向右遍历，如果是1 就tmp++, 如果是0 就res＋＝tmp 最后输出res。
/**************************************** * File Name: 255c.cpp * Author: sky0917 * Created Time: 2014年01月21日 0:09:40 ****************************************/ #include <map> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 200002; int n; long long a[maxn]; inline long long lowbit(int x){ return (x) & (-x); } void add(int pos, long long x){ while (pos <= n){ a[pos] += x; pos += lowbit(pos); } } long long getsum(int pos){ long long sum = 0; while (pos > 0){ sum += a[pos]; pos -= lowbit(pos); } return sum; } struct node{ int p; int di; long long ti; }q[maxn]; bool cmp(node na, node nb){ return na.ti < nb.ti; } int main(){ int va; while (scanf("%d",&n)!=EOF){ for (int i=1; i<=n; i++){ scanf("%d",&va); q[i-1].di = va; q[i-1].p = i; if (va == 0) q[i-1].ti = (long long)i-1; else q[i-1].ti = (long long)n-i; } sort(q, q+n, cmp); memset(a, 0, sizeof(a)); long long res = 0; for (int i=0; i<n; i++){ res += getsum(q[i].p); if (q[i].di == 0){ add(1, 1); add(q[i].p, -1); } else{ add(q[i].p+1, 1); } } printf("%I64d\n",res); } return 0; }
题意：有一个有n个节点的树，每个节点都有一个初始的权值，有m次操作，每次操作有两种：
1 p v 把 p 节点权值+v,把p的孩子-v,把p的孩子的孩子+p,依次类推。
2 p 输出p节点的权值。
分析：每次进行1操作的时候：
+v的节点距离根节点的距离和 p 节点到根节点的距离具有相同的奇偶性
- v的节点则相反。
可以先深搜一次，记录每个节点的时间戳ti, 如果遍历完它的所有后代节点之后的时间戳为tj,
那么这个节点能影响到的范围就是时间戳中[ti, tj]这些节点。
可以建立一个二维树状数组tr[2][maxn]
tr[0][i] 记录距离根节点距离为奇数的节点序列，
tr[1][i] 记录距离根节点距离为偶数的节点序列。
当 1 p v的时候：
就把区间tr[dp[p]][l[p]] 到 tr[dp[p]][r[p]] 这段区间都+v (dp[p] = 0 表示距离为奇数，=1为偶数)
就把区间tr[dp[p]^1][l[p]] 到 tr[dp[p]^1][r[p]] 这段区间都-v
当 2 p 的时候：
输出 tr[dp[p]][l[p]] 的值。
/**************************************** * File Name: 225e.cpp * Author: sky0917 * Created Time: 2014年01月21日 0:51:40 ****************************************/ #include <map> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 200005; int n, m; int tr[2][maxn]; inline int lowbit(int x){ return (x) & (-x); } void add(int pos, int xu, int va){ while (pos <= n){ tr[xu][pos] += va; pos += lowbit(pos); } } int getsum(int xu, int pos){ int s = 0; while (pos > 0){ s += tr[xu][pos]; pos -= lowbit(pos); } return s; } int a[maxn]; struct node{ int to, next; }e[maxn*2+1]; int tot; int head[maxn]; void addedge(int s, int t){ e[tot].to = t; e[tot].next = head[s]; head[s] = tot++; } int v[maxn]; int l[maxn]; int r[maxn]; int ti; int dp[maxn]; void dfs(int u){ l[u] = ti++; v[u] = 1; for (int i=head[u]; i; i=e[i].next){ int k = e[i].to; if (!v[k]){ dp[k] = (dp[u]+1)%2; dfs(k); } } r[u] = ti-1; } int main(){ while (scanf("%d %d",&n,&m)!=EOF){ tot = 1; for (int i=1; i<=n; i++){ scanf("%d",&a[i]); } int ss, tt; for (int i=1; i<n; i++){ scanf("%d %d",&ss,&tt); addedge(ss, tt); addedge(tt, ss); } ti = 1; dp[1] = 0; dfs(1); for (int i=1; i<=n; i++){ add(l[i], dp[i], a[i]); add(l[i]+1, dp[i], -a[i]); } int op; int x, y; while (m--){ scanf("%d",&op); if (op == 1){ scanf("%d %d",&x,&y); add(l[x], dp[x], y); add(r[x]+1, dp[x], -y); add(l[x], (dp[x]+1)%2, -y); add(r[x]+1, (dp[x]+1)%2, y); } else{ scanf("%d",&x); int res = getsum(dp[x], l[x]); printf("%d\n",res); } } } return 0; }