1001：Is Derek lying?
题意：
给你两个人的成绩和答案，判断这两个成绩是否合理。
思路：
先对字符串进行比较，得到相同的选项数same，和不同的选项数diff。如果两个人中最小的成绩小于same，那说明他们相同的选项中有错的。成绩最高的那个对的选项数除了same之外是否超过diff，否者这个成绩是不合理的。要是两个人的成绩大于same，检查他们不相等的成绩是否超过diff。
#include "bits/stdc++.h" using namespace std; char sa[300000 + 10], sb[300000 + 10]; int main(int argc, char const *argv[]) {int t, n;scanf("%d", &t);while (t--) {int ma, mb;scanf("%d%d%d", &n, &ma, &mb);scanf("%s%s", &sa, &sb);int same = 0, diff = 0;for (int i = 0; i < n; i++) {if (sa[i] == sb[i]) same++;else diff++;}if (same > min(ma, mb)) {if (diff < abs(ma - mb)) printf("Lying\n");else printf("Not lying\n");} else {if (diff < ma + mb - 2*same) printf("Lying\n");else printf("Not lying\n");}}return 0; }
1003：Maximum Sequence
题意：
给你两个长度为$n$的序列A$(n\leq a_i \leq 250000)$，B$[1\leq b_i\leq n]$。根据$a_i\leq max\{a_j-j\mid b_k≤j<i\}$, 求出序列A的后n个元素，并且使得后n和个数最大。
思路：
可以看出B序列的顺序对答案没有影响。先把B升序排列，从最小的开始构造，用一个优先队列维护A，每次弹出符合条件的最大值。
#include "bits/stdc++.h" using namespace std; const int MOD = 1e9 + 7; const int maxn = 250010; typedef long long LL; int b[maxn]; struct node {int num, id;friend bool operator < (node a, node b) { return a.num < b.num;} }a; int main(int argc, char const *argv[]) {int n;while (scanf("%d", &n) != EOF) {priority_queue<node> que;for (int i = 0; i < n; i++) {scanf("%d", &a.num); a.id = i + 1;a.num -= a.id;que.push(a);} for (int i = 0; i < n; i++) scanf("%d", &b[i]);sort(b, b + n);LL ans = 0;int cnt = 0;for (int i = 0; i < n; i++) {while (que.top().id < b[i]) que.pop();a.id = ++cnt+n;a.num = que.top().num - a.id;que.push(a);ans = (ans + que.top().num)%MOD;}printf("%lld\n", ans);}return 0; }
1009:TrickGCD
题意：
给你序列A，序列B，满足 1. $1\leq b_i\leq a_i$ 2.For each pair$(l,r),(1\leq l\leq r\leq n),gcd(b_l,b_l+1...b_r)\geq 2$。
思路：利用dp[i]， 表示gcd是i的个数。可以发现对于k*i和k*i + i - 1的i贡献是一样的。用数组cnt[i]记录前缀和。所以区间cnt[k*i]~cnt[k*i +i - 1]的贡献是相同的。统计这段区间的数量，进行乘法计数,得到dp[i]。最后根据容斥原理对于j=k*i，dp[i] -= dp[j]。
#include "bits/stdc++.h" using namespace std; const int MOD = 1e9+7; const int maxn = 2e5 + 100; typedef long long LL; LL cnt[maxn]; int a[maxn]; LL dp[maxn]; LL pow_mod(LL x, LL y) {LL res = 1;LL base = x;while (y) {if (y&1) res = res*base%MOD; y >>= 1;base=base*base%MOD;}return res; } int main(int argc, char const *argv[]) {int T;int kcase = 0;scanf("%d", &T);while (T--) {int n;scanf("%d", &n);int maxx = 0;memset(cnt, 0, sizeof(cnt));memset(dp, 0, sizeof(dp));for (int i = 0; i < n; i++) {scanf("%d", &a[i]); maxx = max(a[i], maxx); cnt[a[i]]++;}for (int i = 1; i <= maxx; i++) cnt[i] += cnt[i - 1];for (int i = maxx; i >= 2; i--) {LL res = 1;if (cnt[i - 1]) {dp[i] = 0; continue;}for (int j = i; j <= maxx; j+=i) {LL sum = cnt[min(maxx, i+j - 1)] - cnt[j - 1];LL s = j/i;if (sum) res = res*pow_mod(s, sum)%MOD;}dp[i] = res;}LL ans = 0;for (int i = maxx; i >= 2; i--) {for (int j = i*2; j <= maxx; j += i) {dp[i] = (dp[i] - dp[j] + MOD)%MOD;}ans = (ans + dp[i] + MOD)%MOD;}printf("Case #%d: %lld\n",++kcase,ans); }return 0; }
1011:Regular polygon
题意：
给你n个整数坐标点，判断这些点可以组成几个正多边形。
思路:
想了下，也百度了下，除了正方形，没有其他的在整数点上，直接暴力枚举对角线。
#include <bits/stdc++.h> using namespace std; const int maxn = 510; struct Point{int x,y; } p[maxn]; double esp = 1e-5; bool vis[maxn][maxn]; int main(int argc, char const *argv[]) {int n;while (scanf("%d", &n) != EOF) {memset(vis, false, sizeof(vis));for(int i = 0;i < n; i++){scanf("%d%d", &p[i].x, &p[i].y);p[i].x += 200; p[i].y += 200;vis[p[i].x][p[i].y] = true;}int ans = 0;for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){if(i == j) continue;double dx1= (p[i].x+p[i].y+p[j].x-p[j].y)/2.0;double dy1= (-p[i].x+p[i].y+p[j].x+p[j].y)/2.0;double dx2= (p[i].x-p[i].y+p[j].x+p[j].y)/2.0;double dy2= (p[i].x+p[i].y-p[j].x+p[j].y)/2.0;int x1 = (int)dx1, y1 = (int)dy1, x2 = (int)dx2,y2 = (int)dy2;if (abs(dx1-x1)<esp&&abs(dx2-x2)<esp&&abs(dy2-y2)<esp&&abs(dy1-y1)<esp)if(vis[x1][y1]&&vis[x2][y2]) ans++;}}printf("%d\n",ans/4);}return 0; }