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

ICPC2023沈阳站(B C D E I J K M)

时间:2024-04-18 23:44:06浏览次数:23  
标签: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\)个数......