国庆集训 1030-1031（未完成）

记一下DAY2的经历 95分惨蛋日

T1：仔细思考了一下，诶，可做，然后就写了，但是中间细节出锅，写了一个半小时最后还WA了一个点，95分（应该是后效性考虑不足，在OJ上交，又T了几个点）

T2：期望？不会，果断跳过

T3，想了大概5分钟？或者不到？想出了正解
但是因为不会写dfs序，就决定log找爸爸比兄弟，拿一些数据小的分数，写完已经过了40分钟
开始调， 发现我出来的答案比样例更优？？？啊！题目看错了，以为可以请多个教练，其实只能请一个
考试还剩下7分钟，赶紧改代码，拼命改，差不多5分钟改完，然后我就交了。
交完发现，完了！交错了！交成了后来 改的过程中 的 中间代码，很好！爆蛋辽！
考试结束交了一下……55分，哎！ $\epsilon =(?o｀?)))$

序列sequence

Input 1
5
4 5 2 3 1
2 3 1 5 4

Output 2
2

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+10;
int A[N], B[N], f[N], n, ans, id;int main() {
    scanf("%d", &n);for(int i = 1; i <= n; i++)    scanf("%d", &A[i]);for(int i = 1, b; i <= n; i++) scanf("%d", &b),  B[b] = i;for(int i = 1; i <= n; i++) f[B[A[i]]] = f[B[A[i]]-1] +1, ans = max(ans, f[B[A[i]]]);printf("%d", n-ans);return 0;
} 

游戏game

Input 1
3 10
1 5 6
-7 3 7
7 9 8

Output 1
9/4

Input 2
7 20
8 4 0 14 1 13 2
19 -11 16 -16 -5 18 -13
15 18 11 14 13 10 5

Output 2
8/15

40分最初版代码

思想是70分的，但是一些处理上面过于愚钝，导致超时，但是可以帮助理解
暴力枚举每两辆车相遇的时间，然后按时间从小到大排序，消去车，直至剩下最后一辆
#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 2e5+10;
int n, L, vi, pi, cnt=0, t1, t2;
ll g;
bool vis[N] ={
    };
struct psx{
    int p, v, a;} car[N];//小车的信息 
struct qyx{
    int a, b, c, d;} q[10*N];//a被b干掉的时间点 inline ll gcd(ll a, ll b){
    return !b ? a : gcd(b, a%b);}
inline ll lcm(ll a, ll b){
    return a>b ? a/gcd(a, b)*b : a/gcd(b, a)*b;}
bool mycmp(psx a, psx b) {
    return a.a>b.a;};inline int compete(int x1,int y1,int x2,int y2) {
    if(!x1 && !y1) return 2;return 1LL*x1*y2 >= 1LL*x2*y1 ? 1 : 2;
}//分数的大小比较 bool mycmp1(qyx a, qyx b) {
    if(compete(a.c, a.d, b.c, b.d)==2) return 1;else return 0;
};inline void init() {
    scanf("%d%d", &n, &L);for(int i = 1; i <= n; i++) scanf("%d", &car[i].p);for(int i = 1; i <= n; i++) scanf("%d", &car[i].v);for(int i = 1; i <= n; i++) scanf("%d", &car[i].a);sort(car+1, car+n+1, mycmp);
}inline void AA(int &T1, int &T2) {
    g = T1>T2 ? gcd(T1, T2) : gcd(T2, T1);T1 /= g;  T2 /= g;
}//分数的化简 inline void BB(int id, int i, int pi, int vi) {
    q[++cnt].a = id;q[cnt].b = i;q[cnt].c = pi;q[cnt].d = vi;
}inline void check1(int id, int i) {
    if(car[id].p == car[i].p) {
    if(id != i) vis[id] = vis[i] = 1;return;}if(car[i].v > 0) {
    vi = car[id].v - car[i].v;if(vi>0 && car[id].p>car[i].p) pi = L-car[id].p+car[i].p;else if(vi>0 && car[id].p<car[i].p) pi = car[i].p-car[id].p;else if(vi<0 && car[id].p>car[i].p) vi = -vi, pi = car[id].p-car[i].p;else if(vi<0 && car[id].p<car[i].p) vi = -vi, pi = L-car[i].p+car[id].p;AA(pi, vi);BB(id, i, pi, vi);}if(car[i].v < 0) {
    vi = car[id].v-car[i].v;pi = car[id].p>car[i].p ? L-car[id].p+car[i].p : car[i].p-car[id].p;AA(pi, vi);BB(id, i, pi, vi);}
}//拳头较硬的车顺时针走 inline void check2(int id, int i) {
    if(car[id].p == car[i].p) {
    if(id != i) vis[id] = vis[i] = 1;return;}if(car[i].v < 0) {
    vi = car[i].v - car[id].v;if(vi>0 && car[id].p>car[i].p) pi = car[id].p-car[i].p;else if(vi>0 && car[id].p<car[i].p) pi = L-car[i].p+car[id].p;else if(vi<0 && car[id].p>car[i].p) vi = -vi, pi = L-car[id].p+car[i].p;else if(vi<0 && car[id].p<car[i].p) vi = -vi, pi = car[i].p-car[id].p;AA(pi, vi);BB(id, i, pi, vi);}if(car[i].v > 0) {
    vi = car[i].v-car[id].v;pi = car[id].p>car[i].p ? car[id].p-car[i].p : L-car[i].p+car[id].p;AA(pi, vi);BB(id, i, pi, vi);}
}//拳头较硬的车逆时针走inline void work() {
    int pi, vi, t1=0, t2=0;for(int id = 1; id <= n; id++) {
    if(car[id].v > 0) for(int i = id+1; i <= n && !vis[id]; i++) if(!vis[i]) check1(id, i);if(car[id].v < 0)for(int i = id+1; i <= n && !vis[id]; i++) if(!vis[i]) check2(id, i);}sort(q+1, q+1+cnt, mycmp1);for(int i = 1; i <= cnt; i++) if(!vis[q[i].a] && !vis[q[i].b])if(compete(t1, t2, q[i].c, q[i].d)==2)t1 = q[i].c, t2 = q[i].d, vis[q[i].b] = 1;printf("%d/%d\n", t1, t2);
}int main() {
    work();return 0;
} 

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 2e5+10;
int n, L, vi, pi, cnt=0, t1, t2;
ll g;
bool vis[N] ={
    };//小车的存在证明
int last[N], next[N];//链表
struct psx{
    int p, v, a;} C[N];//小车的信息 
priority_queue < pair < double, pair <int, int> > > q;//a被b干掉的时间点 
inline ll gcd(ll a, ll b){
    return !b ? a : gcd(b, a%b);}
inline ll lcm(ll a, ll b){
    return a>b ? a/gcd(a, b)*b : a/gcd(b, a)*b;}
bool mycmp(psx a, psx b) {
    return a.p>b.p;};//构环比较inline void init() {
    scanf("%d%d", &n, &L);for(int i = 1; i <= n; i++) scanf("%d", &C[i].p);for(int i = 1; i <= n; i++) scanf("%d", &C[i].v);for(int i = 1; i <= n; i++) scanf("%d", &C[i].a);sort(C+1, C+n+1, mycmp);for (int i = 1; i <= n; i++) last[i] = i-1, next[i] = i+1;last[1] = n;   next[n] = 1;//构建链表 
}inline void AA(int &T1, int &T2) {
    g = T1>T2 ? gcd(T1, T2) : gcd(T2, T1);T1 /= g;  T2 /= g;
}//分数的化简 inline void check(int i, int j) {
    vi = pi = 0;pi = C[i].p-C[j].p;vi = C[i].v-C[j].v;if(vi<0 && pi<0) {
     pi += L; vi = -vi; AA(pi, vi); return; }if(vi<0 && pi>0) {
     vi = -vi; AA(pi, vi); return; }if(vi>0 && pi<0) {
     pi = -pi; AA(pi, vi); return; }if(vi>0 && pi>0) {
     pi = L-pi; AA(pi, vi); return; }
}//处理相遇的时间inline void work() {
    for(int i = 1; i <= n; i++) {
    int j = next[i];check(i, j);q.push(make_pair(-pi*1.0/vi, make_pair(i, j)));}int a=0, b=1;while(q.size()) {
    int i = q.top().second.first;int j = q.top().second.second;q.pop();if (vis[i] || vis[j]) continue;a = pi; b = vi;if(C[j].a<C[i].a) i = j;vis[i] = 1;next[last[i]] = next[i];last[next[i]] = last[i];if (last[i] != next[i]) {
    check(last[i], next[i]);q.push(make_pair(-pi*1.0/vi, make_pair(last[i], next[i])));}}printf("%d/%d", a, b);
}int main() {
    init();work();return 0;
} 

奖牌

Input 1
3 2 1
1 2
3 1
1 2
1 1 1

Output 1
5

Input 2
4 3 2
2 1 4
4 4 3
1 3 3
1 3 2
1 1 2
2 1 1

Output 2
9
10

格点统计

Input 1
4 5 3
2 4
1 2
4 3
3 2
1 4
1 1 4 3
1 2 4 4
2 3 4 4

Output 1
4
7
3

蒟蒻 考场 95分 代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 5e3+2;
int n, m, q;
bool A[N][N];
int D[N], f[N][N], E[N];inline void init() {
    scanf("%d%d%d", &n, &m, &q);for(int i = 1, a, b; i <= m; i++) {
    scanf("%d%d", &a, &b);A[a][b] = 1; }
}inline int get_fa(int x) {
     return D[x]==x ? x : get_fa(D[x]);}inline void get_A() {
    for(int i = 1; i <= n; i++) D[i] = i;for(int i = 1; i < n; i++) {
    //行bool flag = 0;for(int j = 1; j <= n && !flag; j++)//最前列 for(int k = j+1; k <= n && A[i][j]; k++) {
    //后列相同 if(!A[i][k] || D[k]!=k) continue;for(int l = 1; l <= n; l++)//行 if(A[l][k]) A[l][j] = 1;D[k] = j; flag = 1;}}for(int i = 1; i <= n; i++)//列if(D[i] != i) {
    D[i] = get_fa(D[i]);for(int j = 1; j <= n; j++) //行 if(A[j][D[i]]) A[j][i] = 1;}
}inline void get_f() {
    for(int i = 1; i <= n; i++) {
    //行 for(int j = 1; j <= n; j++) //列 f[i][j] = f[i][j-1] + A[i][j];for(int j = 1; j <= n; j++)f[i][j] += f[i-1][j];}
}inline void work() {
    get_A();get_f();
}inline void gout() {
    while( q-- ) {
    int r1, r2, c1, c2;scanf("%d%d%d%d", &r1, &c1, &r2, &c2);printf("%d\n", f[r2][c2]-f[r1-1][c2]-f[r2][c1-1]+f[r1-1][c1-1]);}
}int main() {
    init();work();gout();return 0;
}

考后订正 超时 60分 类似正解 代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 5e3+2;
int n, m, q;
bool A[N][N];
int D[N], f[N][N], E[N];inline int get_fa(int x) {
     return D[x]==x ? x : get_fa(D[x]);}inline void init() {
    scanf("%d%d%d", &n, &m, &q);for(int i = 1; i <= n<<1; ++i) D[i] = i;for(int i = 1, x, y; i <= m; ++i) {
    scanf("%d%d", &x, &y);x = get_fa(x), y = get_fa(y + n);if(x != y)	D[x] = y;}
}inline void get_A() {
    for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j) {
    int x = get_fa(i), y = get_fa(j + n);A[i][j] = (x==y);}
}inline void get_f() {
    for(int i = 1; i <= n; i++) {
    //行 for(int j = 1; j <= n; j++) //列 f[i][j] = f[i][j-1] + A[i][j];for(int j = 1; j <= n; j++)f[i][j] += f[i-1][j];}
}inline void work() {
    get_A();get_f();
}inline void gout() {
    while( q-- ) {
    int r1, r2, c1, c2;scanf("%d%d%d%d", &r1, &c1, &r2, &c2);printf("%d\n", f[r2][c2]-f[r1-1][c2]-f[r2][c1-1]+f[r1-1][c1-1]);}
}int main() {
    init();work();gout();return 0;
}

最后AC代码（之前get_fa没有路径压缩，以及二维数组处理放在了外面）

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 5e3+2;
int n, m, q;
bool A[N][N];
int D[N<<1], f[N][N];inline int get_fa(int x) {
     return D[x]==x ? x : D[x] = get_fa(D[x]);}inline void init() {
    scanf("%d%d%d", &n, &m, &q);for(int i = 1; i <= n<<1; ++i) D[i] = i;for(int i = 1, x, y; i <= m; ++i) {
    scanf("%d%d", &x, &y);x = get_fa(x), y = get_fa(y + n);if(x != y)	D[x] = y;}
}inline void work() {
    for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j) {
    int x = get_fa(i), y = get_fa(j + n);A[i][j] = (x==y);f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + A[i][j];}
}inline void gout() {
    while( q-- ) {
    int r1, r2, c1, c2;scanf("%d%d%d%d", &r1, &c1, &r2, &c2);printf("%d\n", f[r2][c2]-f[r1-1][c2]-f[r2][c1-1]+f[r1-1][c1-1]);}
}int main() {
    init();work();gout();return 0;
}

打字机

Input 1
3
bbc
aacb
cacab

Output 1
17576
456987
11881376

#include<bits/stdc++.h>
#define ll long long
#define mem(x) memset(x, 0, sizeof(x));
using namespace std;const int N = 2e5+2;
const ll mod = 1e9+7;
int q, n;
char ch[N];
int g[N], pre[N][26], f[N];
ll M(ll a){
    return a%mod;}int main() {
    scanf("%d", &q);while (q--) {
    mem(f); mem(pre); mem(g);scanf("%s", ch+1);n = strlen(ch + 1);pre[0][ch[1]-'a'] = 1;for (int i = 1, j = 0; i < n; i++) {
    for (int k = 0; k < 26; k++)pre[i][k] = pre[j][k];pre[i][ch[i+1]-'a'] = i+1;j = pre[j][ch[i+1]-'a'];}for (int i = 1; i <= n; i++) {
    f[i] = 26;for (int j = 0; j < 26; j++)if (ch[i]-'a'!=j) f[i] = M(f[i]+g[i-1]-g[pre[i-1][j]]+mod);g[i] = M(g[i-1] + f[i]);}printf("%lld\n", g[n]);}return 0;
}

士兵训练

Input 1
5 2
1 1 2 2
2 1
1 5
4 2
2 3
3 1
1
2

Output 1
3
3

蒟蒻 55分 RP代码（为了不T，忽略了一种情况，看RP拿分）

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 2e5+10;
struct psx{
    int fa, b,bm1,bm2,bm3, l,lm1,lm2;} p[N];
struct qyx{
    int next, y;} e[N];
int len=0, n, Q;
ll q[5];
int lin[N], son[N];inline void insert(int xx, int yy) {
    e[++len].next = lin[xx];lin[xx] = len;e[len].y = yy;
}inline void init() {
    scanf("%d%d", &n, &Q);for(int i = 2; i <= n; i++) {
    scanf("%d", &p[i].fa);insert(p[i].fa, i);}for(int i = 1; i <= n; i++) scanf("%d%d", &p[i].b, &p[i].l);
}inline void dfs(int k) {
    p[k].lm1 = p[k].l;p[k].bm1 = p[k].b;son[k] = 1;for(int i = lin[k]; i; i = e[i].next) {
    int y = e[i].y; dfs(y);son[k] += son[y];if(p[y].lm1>=p[k].lm1) p[k].lm2=p[k].lm1, p[k].lm1=p[y].lm1;else if(p[y].lm2>p[k].lm2) p[k].lm2=p[y].lm2;if(p[y].bm1>=p[k].bm1) p[k].bm2=p[k].bm1, p[k].bm1=p[y].bm1;else if(p[y].bm1>=p[k].bm2) p[k].bm3=p[k].bm2, p[k].bm2=p[y].bm1;else if(p[y].bm1>p[k].bm3) p[k].bm3=p[y].bm1;if(p[y].bm2>=p[k].bm2) p[k].bm3=p[k].bm2, p[k].bm2=p[y].bm2;else if(p[y].bm2>p[k].bm3) p[k].bm3=p[y].bm2;if(p[y].bm3>p[k].bm3) p[k].bm3=p[y].bm3;}
}inline void prep() {
    dfs(1);
}inline void dfs2(int fa, int son) {
    if(p[fa].lm1>=q[3]) q[5]=q[3], q[3]=p[fa].lm1;else if(p[fa].lm1>q[5]) q[5]=p[fa].lm1;if(p[fa].lm2 > q[5]) q[5] = p[fa].lm2;for(int i = lin[fa]; i; i = e[i].next) {
    int y = e[i].y;if(y == son) continue;if(p[y].lm1>=q[3]) q[5]=q[3], q[3]=p[y].lm1;else if(p[y].lm1>q[5]) q[5]=p[y].lm1;if(p[y].lm2 > q[5]) q[5] = p[y].lm2;}
}inline void get_m1(int x) {
    q[1] = p[x].bm1;q[2] = p[x].bm2;q[4] = p[x].bm3;
}inline void get_m2(int x) {
    q[3] = q[5] = 0;if(n-son[x]==0) return;if(n-son[x]==1) {
     q[3] = p[1].l; return;}else {
    int yy = p[x].fa;int xx = x;while(yy != 1) {
    dfs2(yy, xx);xx = yy;yy = p[yy].fa;}dfs2(1, xx);}
}inline ll work(int x) {
    get_m1(x);//找到管辖范围内最大次大第三大q[1]q[2]q[4]get_m2(x);//找到管辖范围外的最大次大q[3]if(son[x]==1) return 0;if(q[2]+q[3] > q[1]) return q[1];if(q[2]+q[3] ==q[1]) return max(q[4]+q[3], q[2]+q[5]);if(q[2]+q[3] < q[1]) return q[2]+q[3];
}inline void gout() {
    while( Q-- ) {
    int x;scanf("%d", &x);printf("%lld\n", work(x));}
}int main() {
    init();prep();gout();return 0;
}