2021浙江省程式省賽（ACFGJLM題解）

• 2021 年 4 月 20 日
• 筆記
• （cf和訓練賽總結）, （數據結構）kmp, （數據結構）並查集

🎈A

簽到，加起來就行了，記得等於屬於先手贏（2A）

🎈C

題意

給八個點三維坐標，問是否在三維是立方體

思路

八個點的連成56條線，如果是立方體的話有8條，24條，24條相同的線，且都不相同

用map存ll，別開根號就行，有精度問題的(1A)

🎈F

題意

給你t個數據（1000個），兩個數字n，m（1e8），n只能減，m只能加，問最小操作使得m%n==0

思路

m開根號暴力，然後要限制n的範圍，我比賽沒限制，血虧……

因為對稱性就可以降複雜度m變成2 * sqrt（m）（賽後2A）

AC程式碼

#include <bits/stdc++.h>
#define endl '\n'
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
using namespace std;
const int N=3e3+10;
int n,t,m;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        int k=sqrt(m);
        int ans=2e8+10;
        for(int i=1;i<=k;i++){
            if(m%i==0){
                if(n>=i){
                    ans=min(ans,abs(n-i));
                }
                if(n>=m/i){
                    ans=min(ans,abs(m/i-n));
                }
            }
            else{
                if(n>=i){
                    ans=min(ans,abs(n-i)+abs(i-m%i));
                }
                if(n>=m/i+1){
                    ans=min(ans,abs(m/i+1-n)+abs(m/i+1-m%(m/i+1)));
                }
            }
        }
        printf("%d\n",ans);
    }
	return  0;
}
/*
1
31 92
*/

🎈G

題意

遊戲中有一架用規則六邊形拼成的飛機。這個平面上有蜂巢，蜂巢的方向是這樣的：上面和下面都有六邊形節點，左右兩側都有邊緣，蜂巢與其所在行的相鄰蜂巢共用。

隨後的每一行相對於前一行移動半個蜂窩。軸沿水平蜂巢行從左到右。軸相對於軸傾斜60度。坐標軸在蜂巢處相交。

有攻擊和查詢兩種操作。格萊美可以通過一次攻擊行動征服一個蜂巢。

對於一個查詢操作，格萊美想知道她是否在她征服的蜂巢和她沒有征服的蜂巢之間築起了牆，如果她從蜂巢出發在她的領地而不穿過任何牆，她能接觸到多少牆

思路

因為5e5的範圍，暴力連通塊肯定tle，然後想到了並查集

用兩個map分別標記佔領的點（mp）和築起的牆（vis）

然後每次查詢如果這個點兩個佔領的點沒標記過，遍歷六個方向，看vis裡面有沒有牆，如果攻佔過就直接輸出並查集的父親(參考ac程式碼的第二個樣例)

每次攻擊的點（開始給六面牆），遍歷六個方向，如果遍歷的點也是佔領點的話，並起來，然後總數-2即可（因為雙方都失去了一面牆）（比賽沒做血虧，賽後1A）

AC程式碼

#include <bits/stdc++.h>
using namespace std;
struct node{
    int x,y;
    node(){}
    node(int xx,int yy):x(xx),y(yy){}
    friend bool operator<(const node a,const node b){
        if(a.x==b.x)return a.y<b.y;
        return a.x<b.x;
    }
};
const int N=5e5+10;
int f[N],g[N];
int F(int x){
    return f[x]==x?x:f[x]=F(f[x]);
}
int sx[6]={0,0,1,1,-1,-1};
int sy[6]={1,-1,0,-1,0,1};
int main(){
    int n;
    map<node,int>mp,vis;
    scanf("%d",&n);
    int cnt=1;
    for(int i=1;i<=n;i++){
        f[i]=i;g[i]=0;
    }
     for(int i=1;i<=n;i++){
        int x,y,c;
        scanf("%d%d%d",&c,&x,&y);
        if(c==2){
            int star=mp[node(x,y)];
            if(star==0){
                int ge=0;
                for(int j=0;j<6;j++){
                    int xx=x+sx[j],yy=y+sy[j];
                    if(vis[node(xx,yy)]){
                        ge++;
                    }
                }
                printf("%d\n",ge);
            }
            else{
                int u=F(star);
                printf("%d\n",g[u]);
            }
        }
        else{
            int star=mp[node(x,y)];
            if(star){
                continue;
            }
            else{
                mp[node(x,y)]=cnt;star=cnt++;
                if(vis[node(x,y)]){
                    vis[node(x,y)]=0;
                }
                g[star]=6;
                for(int j=0;j<6;j++){
                    int xx=x+sx[j],yy=y+sy[j];
                    int en=mp[node(xx,yy)];//cout<<en<<endl;
                    if(en){
                        int uu=F(star),vv=F(en);
                        if(uu!=vv){
                            f[uu]=vv;
                            g[vv]+=(g[uu]-2);//cout<<g[vv]<<endl;
                        }
                        else{
                            g[vv]-=2;
                        }
                    }
                    else{
                        vis[node(xx,yy)]=1;
                    }
                }
            }
        }
    }
    return 0;
}
/*
8
1 0 0
2 0 0
1 0 2
1 1 2
1 0 3
2 0 3
1 0 1
2 0 0
6
1 -1 2
1 2 0
1 2 -2
1 -1 -1
1 -2 1
2 0 0
*/

🎈J

題意

給你一個n點，m條邊的無向圖，2~n點上有珠寶，每個都有價值ai。從點1開始。穿過每一個邊緣消耗1個單位時間。她可以在頂點撿起一塊珠寶，然後在點1放下。撿起和放下一件珠寶可以立即完成。

此外，她在任何時候最多可以攜帶1件珠寶。

當她放下一件按頂點估價的珠寶時，她得到了它的價值。

現在，對於每一個時間單位，她想知道她能得到的最大值是多少。

思路

bfs找1點到每個點的最短距離，然後多重背包即可(9A)

AC程式碼

先咕了，明天再打

#include <bits/stdc++.h>
#define endl '\n'
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
using namespace std;
const int N=3e3+10;
int ne[N<<1],to[N<<1],head[N];
int vis[N];
int n,m,t;
int dp[N],bu[N];
int a[N],ans[N];
int tot=0;
void add(int u,int v){
    ne[tot]=head[u];
    to[tot]=v;
    head[u]=tot++;
}
struct node{
    int x,y;
    node(){}
    node(int xx,int yy):x(xx),y(yy){}
    friend bool operator<(const node a,const node b){
        return a.y>b.y;
    }
};
void bfs(){
    priority_queue<node>q;
    q.push(node(1,0));
    vis[1]=1;
    while(!q.empty()){
        node k=q.top();q.pop();
        int u=k.x,b=k.y;
        for(int i=head[u];~i;i=ne[i]){
            int v=to[i];
            if(!vis[v]){
                q.push(node(v,b+1));
                bu[v]=(b+1)*2;
                vis[v]=1;
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&t);
    for(int i=2;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<=n;i++){
        vis[i]=0;head[i]=-1;dp[i]=0;bu[i]=inf;ans[i]=0;
    }
    for(int i=0;i<m;i++){
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    bfs();
    for(int i=2;i<=n;i++){
        for(int j=bu[i];j<=t;j++){
            ans[j]=max(ans[j],ans[j-bu[i]]+a[i]);
        }
    }
    for(int i=1;i<=t;i++){
        printf(i==t?"%d\n":"%d ",ans[i]);
    }
	return  0;
}
/*
5 6 5
2 3 4 5
1 2
4 5
5 5
2 3
1 3
3 3
*/

🎈L

思路

沒讀過，隊友告訴我籠統的寫法，我kmp循環節直接過了（2A）

AC程式碼

#include <bits/stdc++.h>
#define endl '\n'
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios::sync_with_stdio(false)
using namespace std;
const int N=1e5+10;
int ne[N];
char s[N];
void GetNext(){
    int l=strlen(s);
    int i=0;int j=-1;
    ne[0]=-1;
    while(i<l){
        if(j==-1 || s[i]==s[j]){
            i++;
            j++;
            ne[i] = j;
        }
        else
            j = ne[j];
    }
    return;
}
int main(){
    int f=1;
    int n;
    scanf("%d",&n);
    scanf("%s",s);
    GetNext();
    for(int i=1;i<=n;i++){
        if(i-ne[i]!=i){
            f=0;break;
        }
    }
    if(f){
        printf("Correct\n");
    }
    else{
        printf("Wrong Answer\n");
    }
    return  0;
}
/*
*/

🎈M

題意

問每個同學可以選擇1~20之內的數，如果別人的數大於自己的獲得10分，不然扣10分，相等不扣分

問最高能獲得分數的概率

思路

10分鐘看完題面，貪逼隊友說全是20，不是就是0.0000嘛，於是交了一發。（1A）

把能寫的題寫完，看I題題解看不懂，告辭