首页 > 其他分享 >2022ccpc广州

2022ccpc广州

时间：2022-11-16 12:44:44浏览次数：53  
标签：广州 return 2022ccpc int res ll long MOD

算是第一场xcpc(?)

现场出了的题：

E. Elevator  冷静分析以下就会发现其实贡献是前面的比当前数小的数和当前数的差值+1,后面的贡献是比当前小的数和当前数的差 于是预处理所有比当前数字小的数的和，前缀比当前数小的个数用树状数组维护一下就好 现场写线段树被卡掉了，光速改了一发树状数组才过的 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 5e5 + 5;

ll t[N * 4], t1[N], t2[N];
int n, m, s[N], ss[N], a[N], cnt;

map<int,int> ma;

#define ls (x << 1)
#define rs (x << 1) | 1


ll query(int x, int l, int r, int ql, int qr) {
    if (qr < ql)
        return 0;
    if (ql <= l && r <= qr) {
        return t[x];
    }
    int mid = (l + r) >> 1;
    ll res = 0;
    if (ql <= mid)
        res += query(ls, l, mid, ql, qr);
    if (qr > mid)
        res += query(rs, mid + 1, r, ql, qr);
    return res;
}
void modify(int x, int l, int r, int p, ll v) {
    if (p < 1 || p > n)
        return;
    if (l == r) {
        t[x] += v;
        return;
    }
    int mid = (l + r) >> 1;
    if (p <= mid)
        modify(ls, l, mid, p, v);
    else
        modify(rs, mid + 1, r, p, v);
    t[x] = t[ls] + t[rs];
}
const int mx = 5e5;
int Tree[mx+10];
int Lowbit(int x){
    return (x&(-x));
}
void Add(int x, int nd){
    for (int i = x ; i<= mx ; i +=Lowbit(i)){
        Tree[i]+=nd;
    }
}
int GetAns(int x){
    int ans = 0;
    for (int i = x ; i ; i -=Lowbit(i))
        ans += Tree[i];
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &s[i]);
        ss[i] = s[i];
    }
    sort(s + 1, s + n + 1);
    for (int i = 1; i <= n; i++) {
        if (s[i] != s[i - 1]) {
            ma[s[i]] = ++cnt;
        }
//        cerr << ma[s[i]] << endl; 
        t1[cnt] += 1;
        t2[cnt] += s[i];
    }
    
    for (int i = 1; i <= n; i++) {
        t1[i] += t1[i - 1];
        t2[i] += t2[i - 1];
    }
    
    for (int i = 1; i <= n; i++) {
        ll p = t1[ma[ss[i]]] - 1;
        ll q = t2[ma[ss[i]]] - ss[i];
        ll res = p * ss[i] - q;
        long long r = GetAns(ma[ss[i]]);
        res += r;
        printf("%lld\n", res > m - 2 ? -1 : res);
        Add(ma[ss[i]],1);
    }
    return 0;
}

H. GameX

发现一定是一个人1,3,5....这么填，另一个人2,4,6....这么填，每次填最小的没被填的数，最后比较谁填到的数字比较大即可。

因为$k$比较小所以直接模拟就好

#include <bits/stdc++.h>
using namespace std;
const int mx = 2e5+5;
int T;
int odd[mx],Even[mx];
int main(){
    cin>>T;
    while (T--){
        int cnt1 = 0,cnt2 = 0;
        int N,K;
        scanf("%d%d",&N,&K); 
        for (int i = 1 ; i <= N ; i ++){
            int x;
            scanf("%d",&x);
            if (x & 1) odd[++cnt1] = x;
            else Even[++cnt2] = x;
        }
        
        sort(odd+1,odd+cnt1+1);
        sort(Even+1,Even+cnt2+1);        
    //    for (int i = 1 ; i<=cnt1 ; i ++)
    //        cout<<odd[i]<<" ";
    //    cout<<endl;
    //    for (int i = 1 ; i <=cnt2 ; i ++)
    //        cout<<Even[i]<<" ";
    //    cout<<endl;
        int pos = 0;
        int nw1 = 1;
        int KK = K;
        if ( odd[1] !=1 ) K--;
        else pos = 1;
        for (int i = 1 ; i <= K+1 ; i ++){
            if(odd[pos] == 0 && pos != 0) {
                nw1+=2;
                continue;
            }
            while (nw1 + 2 == odd[pos+1]){
                pos++;
                nw1 += 2;
            }
            nw1 += 2;
            //cout<<i<<" "<<nw1<<endl;
        }
        K = KK;
        int nw2 = 0;
        pos = 0;
        if (Even[1]!=0) K--;
        else pos = 1;
        for (int i = 1 ; i <= K+1 ; i ++){
            if(pos != 1 && pos != 0 && Even[pos] == 0) nw2 +=2;
            while (nw2 + 2 == Even[pos+1]){
                pos++;
                nw2 += 2;
            }
            nw2 += 2;
            //cout<<i<<" "<<nw2<<endl;
        }
        //cout<<nw1<<" "<<nw2<<endl;
        if (nw1 > nw2) printf("Alice\n");
        else printf("Bob\n");
        for (int i = 1 ; i <= cnt1 ; i ++)
            odd[i] = 0;
        for (int i = 1 ; i <= cnt2 ; i ++)
            Even[i] = 0;
    }
    return 0;
}

L. Station of Fate

签到，没啥好说的(

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int NN = 1e5;
const int MOD = 998244353;

typedef long long ll;

ll ny[N], jc[N];

ll fpow(ll x, int a) {
    ll res = 1;
    while (a) {
        if (a & 1) 
             res = res * x % MOD;
        x = x * x % MOD;
        a >>= 1;
    }
    return res;
}

void init() {
    jc[0] = 1;
    for (int i = 1; i <= NN; i++) {
        jc[i] = jc[i - 1] * i % MOD;
    }
    ny[NN] = fpow(jc[NN], MOD - 2);
    for (int i = NN - 1; i >= 0; i--) {
        ny[i] = ny[i + 1] * (i + 1) % MOD;
    }
}

ll C(int a, int b) {
    return jc[a] * ny[b] % MOD * ny[a - b] % MOD;
}

int main() {
    int T;
    int n, m;
    init();
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        printf("%lld\n", jc[n] * C(n - 1, m - 1) % MOD);
    }
    return 0;
}

M. XOR Sum

首先$xor$肯定考虑拆位，不难发现拆位完之后，每个位置的贡献是$cnt_1$ * $cnt_0$，$cnt_1$表示$1$的个数，$cnt_0$表示$0$的个数。

然后考虑从高位往低位$dp$，有个问题是当前每个数字有一个不大于$m$的限制，对于这个限制，我们多记录一个变量表示当前有几个数还在被限制(数位$dp$的套路)

而高位往低位$dp$的时候，会遇到需要低位进位上来的情况，这种时候我们就把进位堆到低位处理，具体表现为每$dp$一位，进位的数量就要*2

这时候对于每一位，我们枚举这一位填几个$1$，其中有几个被限制的$1$，根据这个可以算出每次有几个数不再被限制，并且可以算出当前这一位会提供几个进位。

这样就可以记忆化出答案。

但是有个比较关键的剪枝：

如果后面所有位置能提供的进位加起来，都不够前面位数所需要的进位的话，就直接退出。

具体在代码里就表现为81*res<=K，$81$是因为显然， 在只有$18$个数字的前提下，9个1，9个0一定是最多的。

然后就过了(

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const int M = 55 * 81;

int K, sn[55], sm[55];
ll n, m;
ll jc[20], ny[20], dp[55][55][M];

ll fpow(ll a, int b) {
    ll res = 1;
    while (b) {
        if (b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

ll C(int a, int b) {
    if (a < 0 || b < 0)
        return 0;
    if (b > a)
        return 0;
    if (b == 0)
        return 1; 
    return jc[a] * ny[b] % MOD * ny[a - b] % MOD;
}

void init() {
    jc[0] = 1;
    memset(dp, -1, sizeof dp);
    for (int i = 1; i <= K; i++) {
        jc[i] = jc[i - 1] * i % MOD;
    }
    ny[K] = fpow(jc[K], MOD - 2);
    for (int i = K - 1; i >= 0; i--) {
        ny[i] = ny[i + 1] * (i + 1) % MOD;
    }
    ny[0] = 1;
}

ll dfs(ll x, int y, int k) { // y个受限制 需要k个进位
    if (k < 0 || k > (x + 1) * 81) {
        return 0;
    }
    if (x < 0) {
        return 1;
    }
    if (dp[x][y][k] != -1)
        return dp[x][y][k];
    ll res = 0;
    if (sm[x] == 1) {
        for (int i = 0; i <= K; i++) { // i个1 
            for (int j = 0, e = min(y, i); j <= e; j++) { // j个受限制的1
                res = (res + dfs(x - 1, j, (k - i * (K - i) + sn[x]) * 2) * C(y, j) % MOD * C(K - y, i - j) % MOD) % MOD;
            }
        }
    } else {
        for (int i = 0; i <= K - y; i++) {
            res = (res + dfs(x - 1, y, (k - i * (K - i) + sn[x]) * 2) * C(K - y, i) % MOD) % MOD; 
        }
    }
    return dp[x][y][k] = res;
}

int main() {
    scanf("%lld%lld%d", &n, &m, &K);
    for (ll i = 0, e = n; e; i++) {
        sn[i] = (e & 1);
        e >>= 1;
    }
    for (ll i = 0, e = m; e; i++) {
        sm[i] = (e & 1);
        e >>= 1;
    }
    init();
    cout << dfs(52, K, 0) << endl;
    return 0;
}

赛后补题：

I. Infection

 

现场想到了一个树上背包+换根+记录前后缀dp值的做法，但是没写完，噔噔咚(

$F[i][j]$表示已经选了初始感染点，在$i$点的子树里感染$j$个的概率，$G[i][j]$表示未选择初始感染点，在$i$子树内感染$j$个的概率

转移式很好写，具体代码直接树上背包即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MOD = 1e9 + 7;
const int N = 2005;

int n, e[N * 2], nex[N * 2], hed[N], ct, siz[N];
int a[N], sa, p[N], np[N], F[N][N], G[N][N], ans[N];

int fpow(ll a, int b) {
    ll res = 1;
    while (b) {
        if (b & 1)
            res = 1ll*res * a % MOD;
        a = 1ll*a * a % MOD;
        b >>= 1ll;
    }
    return res;
}
ll inv;
void dfs(int x, int fa) {
    siz[x] = 1;
    F[x][1] = p[x];
    G[x][1] = 1ll*a[x] * inv % MOD;
    for (int i = hed[x]; i; i = nex[i]) {
        if (e[i] == fa)
            continue;
        dfs(e[i], x);
        for (int j = siz[x] + siz[e[i]]; j >= 1; j--) {
            F[x][j] = 1ll*F[x][j] * np[e[i]] % MOD;
            G[x][j] = 1ll*G[x][j] * np[e[i]] % MOD;
            for (int k = max(j-siz[x],0), end = min(j - 1, siz[e[i]]); k <= end; k++) {
                F[x][j] = (F[x][j] + 1ll*F[e[i]][k] * F[x][j - k] % MOD) % MOD;
                G[x][j] = (G[x][j] + 1ll*F[e[i]][k] * G[x][j - k] % MOD) % MOD;
                G[x][j] = (G[x][j] + 1ll*G[e[i]][k] * F[x][j - k] % MOD) % MOD;
            }
        }    
        siz[x] += siz[e[i]];
    }

    for (int i = 1; i <= siz[x]; i++) {
        ans[i] = (ans[i] + 1ll*G[x][i] * np[fa] % MOD) % MOD;
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        e[++ct] = b, nex[ct] = hed[a], hed[a] = ct;
        e[++ct] = a, nex[ct] = hed[b], hed[b] = ct;
    }
    for (int i = 1; i <= n; i++) {
        int b, c;
        scanf("%d%d%d", &a[i], &b, &c);
        p[i] = 1ll*b * fpow(c, MOD - 2) % MOD;
        np[i] = 1ll*(c - b) * fpow(c, MOD - 2) % MOD;
        sa = (sa + a[i]) % MOD;
    }
    inv = fpow(sa,MOD-2);
    np[0] = 1;
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

K. Middle Point Graph

因为点是随机的，所以四个点被随机成直接共面的概率是$0$

于是就可以开始分类讨论了

对于四元环来说，它的四个中点一定能构成一个平面。

对于三元环来说，选三个中点和随便一个顶点就可以构成一个平面

对于两个中点两个顶点的情况，有一类是在两个共点的边上，取 两个中点+两个顶点((a,b) 和 (b,c) 取 a,c和两个中点)

最后还有一种情况是把一条边的两个顶点和一个中点都取掉，再从剩下的点里面随便抓一个即可。

于是套个三四元环计数的板子即可。

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
int T;
int N,M;
vector <int> G[400005];
long long read(){
    long long ans=0;
    char last=' ',ch=getchar();//last?????????????????????????????
    while(ch<'0' || ch>'9')last=ch,ch=getchar();//???????????????????last?????ch????????
    while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();//??????????????????????
    if(last=='-')ans=-ans;//???????
    return ans;
}
inline void write(int x){
    if (x < 0) x = ~x + 1, putchar('-');
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const long long fish=1e9+7;
int cnt,nex[400005],las[400005],Arrive[400005],d[400005]; 
void jt(int x,int y){
    cnt++;
    nex[cnt]=las[x];
    las[x]=cnt;
    Arrive[cnt]=y;
}
bool cmp(int x,int y){
    return (d[x]==d[y]?x>y:d[x]>d[y]);
}
int Pow(int x,int y){
    int as=1;
    while (y){
        if (y&1) as=1ll*as*1ll*x%fish;
        x=1ll*x*1ll*x%fish;
        y>>=1;
    }
    return as;
}
int inv3=333333336,inv4=250000002,inv2=500000004,inv24=41666667;
int u[500005],v[500005];
int vis[500005],R3[500005],cnt4[500005],cnt3,ans4;
void Get_3(){
    for (int u=1;u<=N;u++){
        for (auto v:G[u]) vis[v]++;
        for (auto v:G[u]) {
            for (auto w:G[v]){
                if (vis[w]){
                    ++R3[w],++R3[u],++R3[v];
                }
            }
        }
        for (auto v:G[u]) vis[v]=0;
    }
    for (int i=1;i<=N;i++)
        (cnt3+=R3[i])%=fish;
    cnt3=1ll*cnt3*1ll*inv3%fish;
    return;
}
void Get_4(){
    for (int u=1;u<=N;u++){
        for (auto v:G[u]){
            if (cmp(u,v)){
                for (auto w:G[v]){
                    if (cmp(u,w)){
                        cnt4[u]+=vis[w];
                        cnt4[v]+=vis[w];
                        cnt4[w]+=vis[w];
                        vis[w]++;
                    }
                }
            }
        }
        for (auto v:G[u]){
            if (cmp(u,v)){
                for (auto w:G[v]){
                    if (cmp(u,w)){
                        cnt4[v]+=--vis[w];
                    }
                }
            }
        }
    } 
    for (int i=1;i<=N;i++)
        (ans4+=cnt4[i])%=fish;
    ans4=1ll*ans4*1ll*inv4%fish;
    //cout<<ans4<<endl;
    return;
}
int Get(){//?????+?????
    int ans=0;
    for (int i=1;i<=N;i++){
        (ans+=1ll*R3[i]*1ll*(d[i]-2)%fish)%=fish;
    }
    return ans;
} 
void init(){
    N=read();M=read();
    int k;
    long long ans = 0;
    //k=read(); 
    for (int i=1;i<=M;i++){
        d[u[i]=read()]++,d[v[i]=read()]++;
    }
    long long inv2 = Pow(2,fish-2);
    for (int i = 1;  i <= N ; i ++){
        (ans += 1ll * d[i] *(d[i]-1)%fish * inv2%fish)%=fish;
    }
    for (int i=1;i<=M;i++)
        if (cmp(u[i],v[i])) G[u[i]].push_back(v[i]);
        else G[v[i]].push_back(u[i]);
    Get_3();
    ans = (ans + 3ll*cnt3%fish)%fish;
    for (int i=1;i<=M;i++)
        if (cmp(u[i],v[i])) G[v[i]].push_back(u[i]);
        else G[u[i]].push_back(v[i]);
    Get_4();
    ans = (ans + ans4)%fish;
    ans = (ans + 1ll*M*(N+M-3)%fish)%fish;
    printf("%lld\n",ans);
    return;
}
void Clear(){
    cnt=0;
    for (int i=1;i<=N;i++){
    R3[i]=cnt4[i]=vis[i]=d[i]=0;
    G[i].clear();
    }
    ans4=0;cnt3=0;
}
int main(){
    T=read();
    while (T--){
        Clear();
        init();
    }
    return 0;
}

 

 

标签：广州,return,2022ccpc,int,res,ll,long,MOD
From： https://www.cnblogs.com/si--nian/p/16895497.html

相关文章

  • 2022CCPC威海站 D - Sternhalma // 状压dp + 记忆化搜索
    题目来源：2022ChinaCollegiateProgrammingContestWeihaiSiteD-Sternhalma题目链接：https://codeforces.com/gym/104023/problem/D题意在一个\(19\)个格子的六边......
  • 广州2022CCPC补题
    IInfection知识点:树上背包第一次写树上背包的题目，没想到就是在区域赛中神奇的是树上背包的复杂度，看起来是\(O(n^3)\)，但是实际计算只有\(O(n^2)\)学会树上背包后可......
  • 2022 CCPC广州 I Infection
    Infection树形dp\(dp[u][k][0/1]\)表示以\(u\)为根的子树，有\(k\)个感染的结点，无/有感染源的概率统计答案的时候要乘上父节点不被传染的概率，表示只传染该子树，不蔓......
  • 2022 CCPC广州 C Customs Controls 2
    CustomsControls2并查集+拓扑看了题解之后补的，题解写挺好的考虑到\(1\)距离相等的点进行并查集合并（指向同一个点的点，到\(1\)的距离相等），缩点后重新建边，判断是否......
  • U3D游戏研发-广州深圳（40-60W）
    岗位要求1.3年以上的客户端(引擎相关)开发经验2.扎实的编程基础,熟悉c/c++,c#,良好的逻辑思维能力,沟通能力,学习能力,有责任心3.对计算机图形学，图形算法,渲染技术......
  • 2022 CCPC 广州站 Alice and Her Lost Cat
    1#include<bits/stdc++.h>2usingnamespacestd;3#definergregister4#definelllonglong5#defineldlongdouble6#defineFOR(i,a,b)for(r......
  • 【广州华锐互动】15年经验的广州VR虚拟现实开发公司，专业vr内容制作平台
    元宇宙的崛起给VR产业带来了新的发展机遇，目前VR市场趋向火热，VR+游戏和VR+电商的应用已经先行一步，技术已相对成熟，而未来，VR将覆盖更多行业，医疗、教育、Live、以及旅游等领域......
  • 2022.11.13：CCPC广州
    补题传送门3题铁这把铁没有沈阳铜那么不甘心（沈阳打完之后，一星期都睡不好），看到了队伍内很多知识点的缺失，不知道在剩下一个正式赛来之前能不能弥补上（跟去年一样，做北大出的......
  • 22.11.13 CCPC 广州站 记录
    上来看A（树上DP），直观认为可做，前后拉着队友研究了两个小时，经过lcx，lgy两次hack正确性，最终基本得到答案思路，因为过于复杂和担心正确性问题不敢写。反思：1.正式比赛中不应该一开......
  • 三维实现广州的行政区划
    效果记录一下智慧广州行政区划制作显示效果需要相机调到正北位置，俯视即可。看似复杂o(╯□╰)o实际上就是画几个​​polygon3d​​再打上marker点就完事了，一般分为几层（最顶......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99