比赛链接：点击打开链接
A:点击打开链接
题意：
问n的排列中多少个不满足 for(int i = 1; i <= n; i++) a[a[i]] == a[i];
显然有 n!-1
所以输出 (n!-1)%mod;
#include <iostream>#include <cstdio>#include <algorithm>#include <string>#include <cmath>#include <cstring>#include <queue>#include <set>#include <map>#include <vector>using namespace std;typedef long long ll;const int N = 100005;const int mod = 1e9+7;template <class T>inline bool rd(T &ret) {char c; int sgn;if(c=getchar(),c==EOF) return 0;while(c!='-'&&(c<'0'||c>'9')) c=getchar();sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0');while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');ret*=sgn;return 1;}template <class T>inline void pt(T x) {if (x <0) {putchar('-');x = -x;}if(x>9) pt(x/10);putchar(x%10+'0');}ll ans[N];int main() {int T; rd(T);ans[1] = 1;for(ll i = 2; i < N; i++){ans[i] = ans[i-1]*i % mod;}int n;while(T–){rd(n);pt((ans[n]-1+mod)%mod); puts("");}return 0;}
B:点击打开链接
题意：
给定n个点的有向图（1为起点，n为终点）
下面每两行给出一个点的出度和所连接的下一个点。
第n个点是没有出度的
图是这样的： 1->2, 1->3, 2->3
第一问：
若存在一种方案使得这个人进入一个点后再也不能到达终点则输出 PRISON , 否则输出 PARDON
第二问：
若这个人可以在图里走无穷步则输出UNLIMITED, 否则输出LIMITED
代码：点击打开链接
C:点击打开链接
双调旅行商
代码：点击打开链接
E:点击打开链接
#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>using namespace std;const int MAX_N = 2000007;int n;int a[MAX_N];long long s[MAX_N], t[MAX_N];int main() {int T;scanf("%d", &T);while (T– > 0) {scanf("%d", &n);for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);}int up = 2 * n;for (int i = n + 1; i <= up; ++i) {a[i] = a[i – n];}long long sum = 0, ans = 0, sum2 = 0;int id = 0;for (int i = 1; i <= n; ++i) {sum += a[i];sum2 += a[i];if (sum < 0) {sum = 0;}if (sum > ans) {ans = sum;id = i;}a[i] = -a[i];}long long sum1 = 0, ans1 = 0;int id1 = 0;for (int i = n; i > 0; –i) {sum1 += a[i];if (sum1 < 0) sum1 = 0;if (sum1 > ans1) {ans1 = sum1;id1 = i;}}//printf("%lld %lld %lld\n", sum, ans1, sum2);ans = max(ans, sum2 + ans1); printf("%lld\n", ans);}return 0;}/*5 3500 Margherita600 Salami700 Hawai800 Speciale900 Doener*/F:点击打开链接#include <iostream>#include <cstdio>#include <algorithm>#include <string>#include <cmath>#include <cstring>#include <queue>#include <set>#include <map>#include <vector>using namespace std;typedef long long ll;const int N = 105;template <class T>inline bool rd(T &ret) {char c; int sgn;if(c=getchar(),c==EOF) return 0;while(c!='-'&&(c<'0'||c>'9')) c=getchar();sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0');while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');ret*=sgn;return 1;}template <class T>inline void pt(T x) {if (x <0) {putchar('-');x = -x;}if(x>9) pt(x/10);putchar(x%10+'0');}int main() {int T, n;ll a, b;scanf("%d", &T);while(T– > 0) {scanf("%d%lld%lld", &n, &a, &b);if(a < b) swap(a, b);int cnt = 0;while(b % 2 != 1) {b /= 2;cnt ++;}printf("%d\n", n-cnt);}return 0;}
G:点击打开链接
题意：
给定[0,n] * [0,m]的二维矩阵
矩阵内有k个绿点
下面k行给出绿点坐标，（保证给出的坐标都不是整数且 0 <= x <= n , 0 <= y <= m
问：
用宽度为1的刷子，一次可以把一行染色或者把一列染色
问最少要使用几次刷子
思路：
二分匹配，把所有点都映射到该点所在的方格的左下角坐标里（即舍弃小数部分）
然后就是一道经典的行列匹配，和排兵布阵一样做法。
代码：点击打开链接
H:点击打开链接
题意：
第一行给出C, n, Q
开始有一个编号[0, C) 的全0序列。
下面Q行操作
status id (询问下标为id的值）
groupchange [l, r] val 把区间[l,r] 每次+1(或-1）val次，，当区间中某一个点达到0或n时则操作停止，输出实际+1(或-1)的值
change id val 同上，只是单点操作。
思路：
裸线段树，维护区间最值和加个lazy标记就可以了
代码：点击打开链接
J:点击打开链接
题意：
可以使用前k种字符(a-z, A-Z, 0-9)，字符串s(len<1e6)问：1、构造一个最小的串使得不为s的子序列，输出最小串的长度 2、这样的串有多少个(mod 1e9+7)
思路：
dp
f[]<-0dp[]<-0now[]<-n+1f[n+1]<-1dp[n+1]<-1forifromndownto0:forjin∑ifdp[now[j]]+1<dp[i]:dp[i]<-dp[now[j]]+1f[i]<-0ifdp[i]==dp[now[j]]+1:f[i]<-f[i]+f[now[j]]now[s[i]]<-i
第一问答案为dp[0]-1
f[0]就是第二问答案
第二个for可以用维护最大次大代替？
我的眼泪流了下来，浇灌了下面柔软的小草，
