首页 > 其他分享 >ICPC2023沈阳站（B C D E I J K M）

ICPC2023沈阳站（B C D E I J K M）

时间：2024-04-18 23:44:06浏览次数：22  
标签：ICPC2023 now 沈阳站 const ll while include getchar

本场金牌线为六题前一半，这里提供难度前八题的题解。

本场真是个细节场，银牌金牌题细节都相当地多。

ICPC2023沈阳站

C:

作为签到题，对这种赛制熟悉不熟悉直接区分了一血时间。谔谔。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define FOR() ll le=e[u].size();for(ll i=0;i<le;i++)
#define QWQ cout<<"QwQ\n";
#define ll long long
#include <vector>
#include <queue>
#include <map>

using namespace std;
const ll N=501010;
const ll qwq=303030;
const ll inf=0x3f3f3f3f;

ll T;
ll n,m;
int du[N];

inline ll read() {
    ll sum = 0, ff = 1; char c = getchar();
    while(c<'0' || c>'9') { if(c=='-') ff = -1; c = getchar(); }
    while(c>='0'&&c<='9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return sum * ff;
}

int main() {
    int ans;
    n = read(); m = read();
    if(n==0 && m==0) ans = 4;
    if(n==0 && m==1) ans = 4;
    if(n==0 && m==2) ans = 6;
    if(n==1 && m==0) ans = 3;
    if(n==1 && m==1) ans = 3;
    if(n==1 && m==2) ans = 4;
    if(n==2 && m==0) ans = 2;
    if(n==2 && m==1) ans = 2;
    if(n==2 && m==2) ans = 2;
    cout<<ans;
    return 0;
}

J：

博弈论，看着挺吓人的，但结论很简单。

手玩一会儿后会发现两个关键点：1、u --> v 后，u会变成叶子；2、u --> v 且 v 是一个叶子，那么操作完树的形态是不会改变的，根据题意，我们不允许 v 是叶子。

所以每进行一个操作就会多一个叶子，统计一下非叶结点的奇偶即可。

有个坑点是 n=2，作为签到题，坑罚时用的，很快就能发现。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define FOR() ll le=e[u].size();for(ll i=0;i<le;i++)
#define QWQ cout<<"QwQ\n";
#define ll long long
#include <vector>
#include <queue>
#include <map>

using namespace std;
const ll N=501010;
const ll qwq=303030;
const ll inf=0x3f3f3f3f;

ll T;
ll n,m;
int du[N];

inline ll read() {
    ll sum = 0, ff = 1; char c = getchar();
    while(c<'0' || c>'9') { if(c=='-') ff = -1; c = getchar(); }
    while(c>='0'&&c<='9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return sum * ff;
}

int main() {
    int x,y;
    n = read();
    for(int i=1;i<n;i++) {
        x = read(); y = read();
        du[x]++; du[y]++;
    }
    int ji = 0, you = 0;
    for(int i=1;i<=n;i++) {
        if(du[i]>1) ji^=1, you = 1;
    }
    if(!(ji&1) && you) cout<<"Alice";
    else cout<<"Bob";
    return 0;
}

E:

好经典的题意。农夫，狼，羊，小船，过河。

这题不需要数学结论，根据数据范围容易写出BFS方程，\(dis[x][y][0/1]\) 表示某岸上羊和狼的数量以及农夫现在的位置，每次过河check一下。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define FOR() ll le=e[u].size();for(ll i=0;i<le;i++)
#define QWQ cout<<"QwQ\n";
#define ll long long
#include <vector>
#include <queue>
#include <map>

using namespace std;
const ll N=501010;
const ll qwq=303030;
const ll inf=0x3f3f3f3f;

ll T;
int X,Y,Q,P;
struct D{
    int di,x,y,cl;
};
queue <D> q;
int dis[111][111][2];

inline ll read() {
    ll sum = 0, ff = 1; char c = getchar();
    while(c<'0' || c>'9') { if(c=='-') ff = -1; c = getchar(); }
    while(c>='0'&&c<='9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return sum * ff;
}

inline bool check(int x,int y,int cl) {
    if(cl==1) {
        return (Y-y)<=((X-x)+P) || x==X;
    }
    else {
        return y<=(x+P) || x==0;
    }
}

int main() {
    X = read(); Y = read(); Q = read(); P = read();
    memset(dis,0x3f,sizeof(dis));
    dis[0][0][0] = 0; q.push({0,0,0,0});
    while(!q.empty()) {
        D now = q.front(); q.pop();
        // cout<<now.di<<" : "<<now.x<<" "<<now.y<<" "<<now.cl<<"\n";
        if(now.cl==0) {
            for(int i=0;i<=X-now.x;i++) {
                for(int j=0;j<=Y-now.y;j++) {
                    if(j+i>Q) break;
                    if(!check(now.x+i,now.y+j,1)) continue;
                    // cout<<" i = "<<i<<" j = "<<j<<endl;
                    if(now.x+i==X) { cout<<now.di+1; return 0; }
                    if(dis[now.x+i][now.y+j][1] > now.di+1)
                    q.push({now.di+1,now.x+i,now.y+j,1}), dis[now.x+i][now.y+j][1] = now.di+1;
                }
            }
        }
        else {
            for(int i=0;i<=now.x;i++) {
                for(int j=0;j<=now.y;j++) {
                    if(j+i>Q) break;
                    if(!check(now.x-i,now.y-j,0)) continue;
                    if(dis[now.x-i][now.y-j][0] > now.di+1)
                    q.push({now.di+1,now.x-i,now.y-j,0}), dis[now.x-i][now.y-j][0] = now.di+1;
                }
            }
        }
    }
    cout<<-1;
    return 0;
}

K:

数据结构好题。

涨分次数最多肯定是涨分场全放前面，假设有 k 个涨分场，我们把涨分多的场放前面，最后一场涨分最小，如果我们把所有的掉分场插到涨分最小的场前面，就有可能得到 k-1，同理 k-2 就是插在倒数第二大的涨分场前面，答案就是搜索掉分场加起来的数值可以覆盖多少加分场。

我撸了棵平衡树，其实权值线段树上二分就行。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define FOR() ll le=e[u].size();for(ll i=0;i<le;i++)
#define QWQ cout<<"QwQ\n";
#define ll long long
#include <vector>
#include <queue>
#include <map>
#define ls son[x][0]
#define rs son[x][1]

using namespace std;
const ll N=801010;
const ll qwq=303030;
const ll inf=0x3f3f3f3f3f3f3f3f;

ll Q;
ll n,m,tot;
ll a[N];
ll fu;
ll rt,fa[N],son[N][2],siz[N],num[N],val[N],sum[N];

inline ll read() {
    ll sum1 = 0, ff = 1; char c = getchar();
    while(c<'0' || c>'9') { if(c=='-') ff = -1; c = getchar(); }
    while(c>='0'&&c<='9') { sum1 = sum1 * 10 + c - '0'; c = getchar(); }
    return sum1 * ff;
}

inline ll touhou(ll x) { return son[fa[x]][1]==x; }
inline void pushup(ll x) { siz[x] = siz[ls] + siz[rs] + num[x]; sum[x] = sum[ls] + sum[rs] + num[x] * val[x]; }
inline void rotate(ll x) {
    ll y = fa[x], z = fa[y], k = touhou(x), w = son[x][k^1];
    son[z][touhou(y)] = x; son[x][k^1] = y; son[y][k] = w;
    fa[w] = y; fa[y] = x; fa[x] = z; pushup(y); pushup(x);
}
inline void splay(ll x,ll goal) {
    while(fa[x]!=goal) {
        ll y = fa[x], z = fa[y];
        if(z!=goal) {
            if(touhou(y)==touhou(x)) rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
    if(!goal) rt = x;
}

inline void insert(ll v) {
    ll x = rt, f = 0;
    while(val[x]!=v && x)
        f = x, x = son[x][val[x]<v];
    if(x) num[x]++, pushup(x);
    else {
        x = ++tot;
        if(f) son[f][val[f]<v] = x;
        fa[x] = f; siz[x] = num[x] = 1;
        val[x] = sum[x] = v;
    }
    splay(x,0);
}

inline void find(ll v) {
    ll x = rt;
    while(val[x]!=v && son[x][ val[x]<v ])
        x = son[x][ val[x]<v ];
    splay(x,0); 
}
inline ll qian(ll v) {
    find(v);
    if(val[rt]<v) return rt;
    ll x = son[rt][0];
    while(rs) x = rs; return x;
}
inline ll hou(ll v) {
    find(v);
    if(val[rt]>v) return rt;
    ll x = son[rt][1];
    while(ls) x = ls; return x;
}

void del(ll v) {
    ll y = qian(v), x = hou(v);
    splay(y,0); splay(x,y);
    if(num[ls]>1) num[ls]--, siz[ls]--, sum[ls]-=val[ls];
    else ls = 0;
    pushup(x); pushup(y);
}

inline ll query(ll v) {
    if(!fu) return 0;
    ll x = rt;
    while(1) {
        if(sum[ls]>=v) x = ls;
        else if(sum[ls]+val[x]*num[x]<v) v -= sum[ls]+val[x]*num[x], x = rs;
        else {v -= sum[ls]; break;}
    }
    splay(x,0);
    ll res = siz[ls]-1;
    res += v/val[rt];
    return res;
}

int main() {
    ll x,wei;
    insert(inf); insert(0);
    n = read(); Q = read();
    for(ll i=1;i<=n;i++) {
        a[i] = read();
        if(a[i]>0) insert(a[i]);
        else fu -= a[i];
    }
    while(Q--) {
        wei = read(); x = read();
        if(a[wei]<=0) fu += a[wei];
        else del(a[wei]);
        if(x<=0) fu -= x;
        else insert(x);
        a[wei] = x;
        // outing();
        cout<<query(fu)+1<<"\n";
    }
    return 0;
}

M:

手玩题。

起始数字不重要，所以我默认从1开始，发现有些无厘头。

其实该从0开始，0才是程序员的浪漫。手玩过后发现两位一循环，一个循环节是 0->1->3->2->0，每多一位就把前面的部分复制 4 遍（要注意纯0只会出现一次）。第 k 次到达 0 的步数是 \(4^1+4^2+4^3+...+4^k\) ，其他的数字，到达次数取决于末尾 0 的个数，设题目所给次数为x，x要小于等于0的个数加一。我们可以把前面 1 的步数计算完，再加上 \(4^1+4^2+...+4^x\)。

细节还挺多，感觉导致这场金牌线题数少的最大元凶就是这题，但是个不错的手玩题。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define FOR() ll le=e[u].size();for(ll i=0;i<le;i++)
#define QWQ cout<<"QwQ\n";
#define ll long long
#include <vector>
#include <queue>
#include <map>

using namespace std;
const ll N=2201010;
const ll qwq=303030;
const ll inf=0x3f3f3f3f;
const ll p=1000000007, in3=333333336;

ll T;
ll n,m,k;
char s[N],t[N];
ll a[N],b[N],c[N];
ll ans;
ll f[N];

inline ll read() {
    ll sum = 0, ff = 1; char c = getchar();
    while(c<'0' || c>'9') { if(c=='-') ff = -1; c = getchar(); }
    while(c>='0'&&c<='9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return sum * ff;
}

inline ll ksm(ll aa,ll bb) {
    ll sum = 1;
    while(bb) {
        if(bb&1) sum = sum * aa %p;
        bb >>= 1; aa = aa * aa %p;
    }
    return sum;
}

void chushihua() {
    ans = 0;
}

inline ll duan(ll i) {
    if(i<=N-10) return f[i];
    return (ksm(4,i)-1+p) * in3 %p;
}

int main() {
    f[1] = 1;
    for(int i=1;i<=N-10;i++) f[i] = (f[i-1] * 4ll + 1ll) %p;
    T = read();
    while(T--) {
        chushihua();
        scanf("%s%s",s+1,t+1); n = strlen(s+1); m = strlen(t+1);
        k = read();
        ll len = max(n,m);
        if(len&1) len++;
        for(ll i=1;i<=len;i++) {
            if(i<=n) a[i] = s[n+1-i] - '0'; else a[i] = 0;
            if(i<=m) b[i] = t[m+1-i] - '0'; else b[i] = 0;
        }
        len >>= 1;
        int you = 0;
        for(ll i=1;i<=len;i++) {
            int yi = a[(i<<1)-1] ^ b[(i<<1)-1];
            int er = a[i<<1] ^ b[i<<1];
            if(yi && er) c[i] = 2;
            if(yi && !er) c[i] = 1;
            if(!yi && er) c[i] = 3;
            if(!yi && !er) c[i] = 0;
            if(c[i] && !you) you = i;
        }
        if(!you) {
            cout<<(duan(k)-1+p)%p<<"\n";
            continue;
        }
        if(k>you) { cout<<"-1\n"; continue; }
        c[k-1] = 4;
        for(ll i=1;i<=len;i++) {
            (ans += c[i] * duan(i) %p) %= p;
        }
        cout<<(ans%p+p)%p<<"\n";
    }
    return 0;
}

B:

金牌题一。

这题我做过一个简化版本，出题人应该就是根据那一道题改编的。

简化版的那道题是求数字一上一下的排列数量，可以 n^2 dp 解决，\(f[i][j]\) 表示填写到第 i 个数字，第 i 个数字在前面这些数字中排名第 j，在转移时我们不考虑每个数字的绝对数值，而是考虑它们的相对数值，也就是枚举下一个数字插在哪个位置。

这题数据范围很友好，n^4 甚至 n^5 都能过，为了求字典序第 k 大，我们就从第一位填1开始，每次计算下剩余数位有多少方案，每一位扫一遍，n^2可以扫完。怎么统计剩余数位的方案呢，我们把数值看成横轴，位置看成纵轴，我们已经确定了前几个位置的数值，那么横轴上留下一些剩余数值供我们填写，这些数值就构成一上一下的关系，我们用我们上面的思路可以轻松地求出。

思路比较流程，但是细节比较多，比如横轴上留下数值的位置也是有限制的，建议自己手玩一下。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define FOR() ll le=e[u].size();for(ll i=0;i<le;i++)
#define QWQ cout<<"QwQ\n";
#define ll long long
#include <vector>
#include <queue>
#include <map>

using namespace std;
const ll N=201010;
const ll qwq=303030;
const ll inf=1e18;
const ll p=1000000007, in3=333333336;

ll n,K;
ll f[111][111];
ll dp[111][111];
ll da = 50;
ll yi;
ll ans[111], a[111];

inline ll read() {
    ll sum = 0, ff = 1; char c = getchar();
    while(c<'0' || c>'9') { if(c=='-') ff = -1; c = getchar(); }
    while(c>='0'&&c<='9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return sum * ff;
}

void qiu() {
    for(int i=0;i<=da;i++) f[i][0] = 1;
    for(int i=0;i<=da;i++) {
        memset(dp,0,sizeof(dp));
        for(int k=1;k<=i+1;k++) dp[1][k] = 1;
        f[i][1] = i+1;
        for(int j=2;j<=da;j++) {
            if(j&1) {
                for(int k=2;k<=i+j;k++) {
                    for(int l=1;l<=k-1;l++) {
                        dp[j][k] += dp[j-1][l];
                        if(dp[j][k] > inf) { dp[j][k] = inf; break; }
                    }
                }
            }
            else {
                for(int k=1;k<i+j;k++) {
                    for(int l=k;l<i+j;l++) {
                        dp[j][k] += dp[j-1][l];
                        if(dp[j][k] > inf) { dp[j][k] = inf; break; }
                    }
                }
            }
            for(int k=1;k<=i+j;k++) {
                f[i][j] += dp[j][k];
                if(f[i][j] > inf) { f[i][j] = inf; break; }
            }
        }
    }
}

ll check() {
    ll res = 1;
    ll len = 0, sum = 0;
    for(int j=1;j<=n;j++) {
        if(!a[j]) len++;
        if(j==n || a[j+1]) {
            if(inf / res < f[sum][len]) { res = inf; break; }
            res *= f[sum][len];
            sum += len;
            len = 0;
        }
    }
    return res;
}

int main() {
    qiu();
    n = read(); K = read();
    ll now = 0;
    for(int j=1;j<=n;j++) {
        if((K - now - 1) / f[0][j-1] < f[j-1][n-j]) { yi = j; break; }
        now += f[0][j-1] * f[j-1][n-j];
    }
    if(!yi) { cout<<-1; return 0; }
    ans[1] = yi;
    a[yi] = 1;
    for(int i=2;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            bool ke = 0;
            if(j==1 && a[2]) ke = 1;
            if(j==n && a[n-1]) ke = 1;
            if(a[j-1] && a[j+1]) ke = 1;
            if((j&1) == (yi&1)) ke = 1;
            if(a[j]) ke = 0;
            if(!ke) continue;
            a[j] = i;
            if(now + check() >= K) { ans[i] = j; break; }
            now += check();
            a[j] = 0;
        }
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
    return 0;
}

D:

金牌题二。

S中选一段字符串，T中选一段字符串，拼起来要求是一个平方串。

数据范围是 n^2，于是开始思考各种枚举，我们设 S 中选出的串为 ABA 的形式，T中选出串为 B 的形式（T长则反过来再计算一次就行）。

我们 n^2 的枚举位置，一个是第一个 A 的左端 \(l1\)，一个是第二个 A 的左端 \(l2\)，这两个位置的后缀串的LCP，决定了 B 串的最小要求长度。统计有多少满足的 B 串可以先 n^2 预处理 S 中每一个位置和 T 中每一个位置的 LCS（在S的每个位置上记录各个LCS数值的出现次数），统计答案就用 \(l2\) 这个位置记录的数据，计算大于 B 串最小长度要求的串的贡献和（经典的两个前缀和统计三角面积）。

感觉，还是有很多细节。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define FOR() ll le=e[u].size();for(ll i=0;i<le;i++)
#define QWQ cout<<"QwQ\n";
#define ll long long
#include <vector>
#include <queue>
#include <map>

using namespace std;
const ll N=201010;
const ll qwq=303030;

ll n,m;
char s[5050],t[5050],z[5050];
int f[5050][5050],g[5050][5050];
ll a[5050],b[5050];
ll ans;

inline ll read() {
    ll sum = 0, ff = 1; char c = getchar();
    while(c<'0' || c>'9') { if(c=='-') ff = -1; c = getchar(); }
    while(c>='0'&&c<='9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return sum * ff;
}

void solve(ll cl) {
    memset(f,0,sizeof(f));
    memset(g,0,sizeof(g));
    for(ll i=n;i>=1;i--) {
        for(ll j=n;j>=1;j--) {
            if(s[i]==s[j]) f[i][j] = f[i+1][j+1] + 1;
        }
    }
    for(ll i=1;i<=n;i++) {
        for(ll j=1;j<=m;j++) {
            if(s[i]==t[j]) g[i][j] = g[i-1][j-1] + 1;
        }
    }
    for(ll i=1;i<=n;i++) {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(ll j=1;j<=m;j++) {
            a[ g[i][j] ]++;
            b[ g[i][j] ]+=g[i][j];
        }
        for(ll j=m;j>=1;j--) a[j] += a[j+1], b[j] += b[j+1];
        for(ll j=1;j<=i;j++) {
            ll wo = f[i+1][j];
            ll zong = (i-j+1);
            ll L = max(1ll,zong-wo), R = (cl==1) ? zong : zong-1;
            if(L>R) continue;
            ans += a[R+1] * (R-L+1);
            ans += (b[L] - b[R+1]) - (a[L] - a[R+1]) * (L-1);
        }
    }
}

int main() {
    scanf("%s%s",s+1,t+1); n = strlen(s+1); m = strlen(t+1);
    solve(1);
    reverse(s+1,s+n+1);
    reverse(t+1,t+m+1);
    for(ll i=1;i<=n;i++) z[i] = s[i];
    for(ll i=1;i<=m;i++) s[i] = t[i];
    for(ll i=1;i<=n;i++) t[i] = z[i];
    swap(m,n);
    solve(0);
    cout<<ans;
    return 0;
}

I:

金牌题三。

其实不是很难，分类讨论也不是说逆天地多，这题能成为金牌题和榜歪有一定的关系。

首先这题一个很关键的点：肯定有一个矩形能够覆盖两个角。然后这题就能顺利进行下去了。

讨论时我们默认覆盖行的矩形比覆盖列的矩形多，否则swap所有数据，可以少一半的码量。

然后是讨论：

1、有三个覆盖行的矩形：就类似于三个横扛上下滑动。因为要覆盖四个角所以至少有两个横杠是需要固定在角上的，所以就只有一个横杠能上下滑（注意有三个杠都跑到角落的情况，需要容斥）。这个其实是最复杂最难算的情况。

2、有两个覆盖行的矩形：两个横杠上下滑，一个需要固定在上面，一个需要固定在下面。如果中间还有缝隙的话，剩余一个没有覆盖行的矩形肯定是做不到的；如果中间没有缝隙，剩余一个矩形位置随意。

3、一个覆盖行的矩形，一个覆盖列的矩形：无论它俩滑到上下左右的任意位置，留下的空都是固定的，而且留下了一个角导致剩余的矩形位置也固定了，答案不是0就是4。

4、一个覆盖行的矩形：除了这个杠需要覆盖两个角以外，剩下的两个矩形也需要各覆盖一个角，答案不是0就是4。

5、没有覆盖行或列的矩形：答案是0。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define FOR() ll le=e[u].size();for(ll i=0;i<le;i++)
#define QWQ cout<<"QwQ\n";
#define ll long long
#include <vector>
#include <queue>
#include <map>

using namespace std;
const ll N=201010;
const ll qwq=303030;
const ll p=1000000007;

ll T;
ll n,m,H,W;
ll a1,b1,a2,b2,a3,b3;

inline ll read() {
    ll sum = 0, ff = 1; char c = getchar();
    while(c<'0' || c>'9') { if(c=='-') ff = -1; c = getchar(); }
    while(c>='0'&&c<='9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return sum * ff;
}

void solve1() {
         if(a1*b1==n*m) cout<<(n-a2+1) * (m-b2+1) %p * (n-a3+1) %p * (m-b3+1) %p<<"\n";
    else if(a2*b2==n*m) cout<<(n-a1+1) * (m-b1+1) %p * (n-a3+1) %p * (m-b3+1) %p<<"\n";
    else if(a3*b3==n*m) cout<<(n-a1+1) * (m-b1+1) %p * (n-a2+1) %p * (m-b2+1) %p<<"\n";
}

void solve2() {
    if(W==3) { swap(n,m); swap(a1,b1); swap(a2,b2); swap(a3,b3); }
    ll res = 0;
    if(b1+b2+b3<m) { cout<<"0\n"; return ; }

    if(b1+max(b2,b3)>=m) res += 2;
    if(b2+max(b1,b3)>=m) res += 2;
    if(b3+max(b1,b2)>=m) res += 2;

    if(b1+b2>=m) res += 2 * (m-b3-1);
    else {
        ll L = max(2ll,m-b2-b3+1);
        ll R = min(m-b3,b1+1);
        if(L<=R) res += 2 * (R-L+1);
    }
    if(b1+b3>=m) res += 2 * (m-b2-1);
    else {
        ll L = max(2ll,m-b3-b2+1);
        ll R = min(m-b2,b1+1);
        if(L<=R) res += 2 * (R-L+1);
    }
    if(b2+b3>=m) res += 2 * (m-b1-1);
    else {
        ll L = max(2ll,m-b3-b1+1);
        ll R = min(m-b1,b2+1);
        if(L<=R) res += 2 * (R-L+1);
    }
    cout<<(res%p+p)%p<<"\n";
}

void solve3() {
    if(W==2) { swap(n,m); swap(a1,b1); swap(a2,b2); swap(a3,b3); }
    ll A, B, C, D;
    if(a3!=n) A = b1, B = b2, C = a3, D = b3;
    if(a2!=n) A = b1, B = b3, C = a2, D = b2;
    if(a1!=n) A = b2, B = b3, C = a1, D = b1;
    if(A+B<m) { cout<<"0\n"; return ; }
    cout<<2*(n-C+1)%p*(m-D+1)%p<<"\n";
}

void solve4() {
    if((a1+a2+a3>=2*n) && (b1+b2+b3>=2*m)) cout<<"4\n";
    else cout<<"0\n";
}

void solve5() {
    if(W==1) { swap(n,m); swap(a1,b1); swap(a2,b2); swap(a3,b3); }
    if(a2==n) swap(a1,a2), swap(b1,b2);
    if(a3==n) swap(a1,a3), swap(b1,b3);
    if(b1+b2<m || b1+b3<m) { cout<<"0\n"; return ; }
    if(a2+a3<n) { cout<<"0\n"; return ; }
    cout<<"4\n";
}

int main() {
    T = read();
    while(T--) {
        n = read(); m = read();
        a1 = read(); b1 = read(); a2 = read(); b2 = read(); a3 = read(); b3 = read();
        if(a1*b1==n*m || a2*b2==n*m || a3*b3==n*m) { solve1(); continue; }
        H = W = 0;
        if(a1==n) H++; if(a2==n) H++; if(a3==n) H++;
        if(b1==m) W++; if(b2==m) W++; if(b3==m) W++;
        if(!H && !W) { cout<<"0\n"; continue; }
        if(H==3 || W==3) { solve2(); continue; }
        if(H==2 || W==2) { solve3(); continue; }
        if(H==1 && W==1) { solve4(); continue; }
        if(H+W==1) { solve5(); continue; }
    }
    return 0;
}

标签：ICPC2023,now,沈阳站,const,ll,while,include,getchar
From： https://www.cnblogs.com/maple276/p/18144780

相关文章

  • ICPC2023杭州站题解（B D E F G H J M）
    本场金牌数量较其他场多（45枚），但金牌线题数不多。五题为分水岭，五道简单题过后所有题均为金牌题，其中有四道可做，即ABEF，做出任意一道即可拿金牌。这里提供除A题以外的所有可做题的题解。ICPC2023杭州站：M：加入比当前选择的所有数大的数一定会让平均值上升，因此答案数列中，V图中的......
  • ICPC2023南京站题解（A C D F G I L M）
    本场金牌线为7题前一半。做出8题可稳金牌，这里是难度前8题的题解。ICPC2023南京站I:签到题。#include<bits/stdc++.h>#definelllonglong#defineQWQcout<<"QwQ"<<endl;#defineFOR()llle=e[u].size();for(lli=0;i<le;i++)usingnamespacestd;constllN=501010;......
  • ICPC2023 陕西邀请赛 题解
    G-PermutationQuestion找到一个排列\(p\)，使得\(\prod_{i=1}^nlcm(p_i,p_{(imodn)+1})\)最大Solution考虑到\(x\)和\(x-1\)必然是互质的所以顺序排列即可Code#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;cin>>n;for(inti......
  • ICPC2023 杭州 题解
    M-V-DiagramSolution很显然，连续的子序列的一段肯定是包括最左边或最右边的其中一个点Code#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constllinf=1ll<<60;intmain(){intt;cin>>t;while(t--){ intn;cin>>n;......
  • BUPT 2024 Spring Training #3（ICPC2023 杭州站）Ag复盘
    D-OperatorPrecedence求一个长度为\(2n\)的序列\(a_{2n}\)满足条件\((a_1×a_2)+(a_3×a_4)+\ldots+(a_{2n-1}×a_{2n})=a_1×(a_2+a_3)×\ldots×(a_{2n-2}+a_{2n-1})×a_{2n}\)solution构造题显然找特殊规律。考虑到乘法构造难度大于加法，可以从乘法开始考虑。......
  • 【补题记录】ICPC2023 Jinan
    【补题记录】ICPC2023JinanContestLink:https://qoj.ac/contest/1472.Problems:https://sua.ac/wiki/2023-icpc-jinan/contest-zh.pdf.Solution:https://qoj.ac/download.php?type=attachments&id=1472&r=1.A.ManyManyHeadsconstintN=1e5+10;intT;str......
  • ICPC2023 杭州站游记
    Day-2周五早八的飞机，周四晚上就润去机场旁边的酒店了。队长说昨晚没睡好，不到九点就先睡了，但是十二点左右就睡醒了。睡醒之后又点了外卖吃，这下完全不困了，玩手机玩到三点顶不住就睡了。和队长聊天，目标都是守银。Day-1本来定的5:45的闹钟，5:43刚好醒来，简单收拾一下就出发了，......
  • ICPC2023重庆市赛游记
    人生总是由遗憾构成的Day-1比赛前2天，由于dlh和fq需要考四级，所以我提前到重庆来"旅游"。来的路上vp了一场codeforsediv.2，1.5h写了3题，手感不是很好（也有可能题太阴间）来到重庆，天下着小雨，但是我还是开始我的CityWalk--ChongQing，我循着5年前的足迹走在解放碑......
  • ICPC2023深圳部分题解（A,D,E,F,G,K,L）
    目录正题A一道好题题目大意解题思路D机器人兄弟题目大意解题思路E二合一题目大意解题思路F见面礼题目大意解题思路G相似基因序列问题题目大意解题思路K四国军棋题目大意解题思路LMary有颗有根树题目大意解题思路正题好像还没上gym所以放不了题目链接，深圳这场的题目我觉......
  • 2021 ICPC 沈阳站 补题
    E.EdwardGaming,theChampion签到题，扫一遍判断就行F.EncodedStringsI简单题，先\(O(n^2)\)大力预处理出来所有字符串，然后直接sortB.BitwiseExclusive-ORSequence题意简述一个需要填数的序列，给定多个限制，每个限制形如\(a_u\oplusa_v=a_w\)表示第\(u\)个数......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99