个人赛3补题

所以one type指的是只能买一种糖果，且只能买一个orz

#include <iostream>
#include <stdio.h>
//#include <windows.h>
using std::max;
const int MAXN = 105;
int d[MAXN], c[MAXN], cost[MAXN];
int main () {int n, s, ans = -1;scanf("%d%d",&n,&s);s *= 100;for (int i = 0; i < n; i ++) {scanf("%d%d",&d[i],&c[i]);cost[i] = d[i] * 100 + c[i];if (cost[i] <= s) ans = max(ans,(100 - c[i]) % 100); }printf("%d\n",ans);//system("pause");return 0;
}

#include <iostream>
#include <stdio.h>
#include <algorithm>
using std::sort;
const int MAXN = 1e5 + 5;
int h[MAXN];
int main () {int n, ener = 0, mon = 0;scanf("%d",&n);for (int i = 1; i <= n; i ++) scanf("%d",&h[i]);for (int i = 0; i < n; i ++) {ener += h[i] - h[i + 1];if (ener < 0) {mon -= ener;ener = 0;}}printf("%d\n",mon);
}

• 比赛过程写的错误题解

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
//#include <windows.h>
using std::sort;
using std::max;
using std::swap;
const int MAXN = 2000 + 5;
int map[MAXN][MAXN], use[MAXN][MAXN];
long long dia[2 * MAXN][2];
int n;
struct node {long long sum;int inx, iny;
}ans, ans1, ans2;
//不能放在同一对角线上
bool check(int x, int y) {if ((!use[x][y]) && (dia[x + y][0] > 0) && (dia[x - y + n][1] > 0)) return true;return false;
}
struct node work() {for (int i = 1; i <= n; i ++) {for (int j = 1; j <= n; j ++) {if (check(i,j)) {if (dia[i + j][0] + dia[i - j + n][1] - map[i][j] > ans.sum) {ans.sum = dia[i + j][0] + dia[i - j + n][1] - map[i][j];ans.inx = i;ans.iny = j;}}}}return ans;
}
int main () {int answer = 0, x1, y1, x2, y2;scanf("%d",&n);for (int i = 1; i <= n; i ++) {for (int j = 1; j <= n; j ++) {scanf("%d",&map[i][j]);dia[i + j][0] += map[i][j];dia[i - j + n][1] += map[i][j];}}ans.sum = -1;ans1 = work();x1 = ans1.inx;y1 = ans1.iny;use[x1][y1] = 1;dia[x1 + y1][0] = -1;dia[x1- y1 + n][1] = -1;ans.sum = -1;ans2 = work();answer = ans1.sum + ans2.sum;x2 = ans2.inx;y2 = ans2.iny;if (x1 > x2) {swap(x1,x2);swap(y1,y2);}printf("%lld\n",answer);printf("%d %d %d %d\n",x1, y1, x2, y2);//system("pause");
}

错误在于没有正确设定避免一个cell同时被两个bishop攻击的条件，并非排除已选择的cell的对角线上的所有元素即可。

• 正确题解
  正确的条件应为两个不同的cell的行列之和奇偶不同
  关于这个的推导见下图
  
  这题还有另一种方法就是如图，选取对角线和最大的两条，求其交点坐标
  （最后改的时候还因为answer定义成了intWA了好多次orz）

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
//#include <windows.h>
using std::sort;
using std::max;
using std::swap;
const int MAXN = 2000 + 5;
int map[MAXN][MAXN];
long long dia[2 * MAXN][2];
int n;
struct node {long long sum;int inx, iny;
}ans[2];
void work() {for (int i = 1; i <= n; i ++) {for (int j = 1; j <= n; j ++) {if (dia[i + j][0] + dia[i - j + n][1] - map[i][j] > ans[(i + j) % 2].sum) {ans[(i + j) % 2].sum = dia[i + j][0] + dia[i - j + n][1] - map[i][j];ans[(i + j) % 2].inx = i;ans[(i + j) % 2].iny = j;}}}
}
int main () {int x1, y1, x2, y2;long long answer = 0;scanf("%d",&n);for (int i = 1; i <= n; i ++) {for (int j = 1; j <= n; j ++) {scanf("%d",&map[i][j]);dia[i + j][0] += map[i][j];dia[i - j + n][1] += map[i][j];}}ans[0].sum = -1;ans[1].sum = -1;work();answer = ans[0].sum + ans[1].sum;x1 = ans[0].inx;y1 = ans[0].iny;x2 = ans[1].inx;y2 = ans[1].iny;if ((x1 > x2) || (x1 == x2 && y1 > y2)) {swap(x1,x2);swap(y1,y2);}printf("%lld\n",answer);printf("%d %d %d %d\n",x1, y1, x2, y2);//system("pause");
}

题D Gargari and Permutations
由于第1~k个数组均为1 ~ n的排列，故最大公共子序列一定包含在第一个数组内。
对于每一个数组，对于每一个序列<i,j>（j < i），判断对应的数字num[1][i]是否也在num[1][j]之后，如果有任一个数组不满足，那么该数字不在最大公共子序列里，否则最大公共子序列长度+1.

#include <iostream>
#include <string.h>
#include <algorithm>
//#include <windows.h>
using std::max;
const int MAXN = 1005;
int pos[6][MAXN];
int num[6][MAXN];
int dp[MAXN];
int main()
{int n,k;scanf("%d%d",&n,&k);for (int i = 1; i <= k; i ++) {for(int j = 1; j <= n; j ++) {scanf("%d",&num[i][j]);pos[i][num[i][j]]=j; //pos[i][num[i][j]]含义为值num[i][j]在第i个数组的位置}}for (int i = 0; i <= 1005; i ++) dp[i] = 1;for (int i = 1; i <= n; i ++) {for (int j = 1; j <= i - 1; j ++){bool flag = 1;for (int s = 1; s <= k; s++){if (pos[s][num[1][i]] < pos[s][num[1][j]]) { //第一个数组一定包含最长公共子序列flag = 0;}}if(flag && dp[i] < dp[j] + 1){dp[i] = dp[j] + 1;}}}int ans = 0;for(int i = 1; i <= n; i ++)ans = max(ans,dp[i]);printf("%d\n",ans);//system("pause");return 0;
}