Codeforces Round 264 (Div. 2)

Diposting di | Edited on

传送门

A - Caisa and Sugar （签到）

B - Caisa and Pylons （根据能量守恒定理hhh）

C - Gargari and Bishops （模拟）

题意

给出一个棋盘你可以放两个皇后，皇后可以攻击和他一个对角线的对象。但是两个皇后不能攻击到同一个目标 求出皇后攻击目标后获得的最大值

思路

首先对于对角线正对角线的x+y都是固定的，反对角线的X-Y都是固定的

然后我们就枚举对角线的值就行，

通过观察发现不相交的对角线他们的x+y的奇偶不同。所以我们分别求出最大即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e3+50;

ll a[maxn][maxn];
ll maxL[maxn*2];
ll maxR[maxn*2];
int main(){

    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
            maxL[i+j]+=a[i][j];
            maxR[i-j+n]+=a[i][j];
        }
    }
    ll even=0,odd=0,sx,sy,ex,ey;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if((i+j)&1){
                if(maxL[i+j]+maxR[i-j+n]-a[i][j]>=odd){
                    odd=maxL[i+j]+maxR[i-j+n]-a[i][j];
                    sx=i;sy=j;
                }
            }
            else{
                if(maxL[i+j]+maxR[i-j+n]-a[i][j]>=even){
                    even=maxL[i+j]+maxR[i-j+n]-a[i][j];
                    ex=i;ey=j;
                }
            }
        }
    }
    printf("%lld\n",even+odd);
    printf("%lld %lld %lld %lld\n",sx,sy,ex,ey);
    return 0;
}

D - Gargari and Permutations (DP)

题意

求出K个排列的LCS

思路

两种解法：

DP：首先对于第一个排列他们之间的大小关系肯定是固定的，所以我们可以枚举第一个排列的大小关系，判断这个关系在其他k-1个排列中是否也符合 如果符合那么后者的答案就可以从前者身上转移而来 $dp[i]=max(dp[i],dp[j]+1)$

dfs： 前半部分相同，后面改成每一个符合的关系一起建图。对于每个点求出一个最长路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//dp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e3+50;
int a[6][maxn];
int id[6][maxn];
int dp[maxn];
int now[maxn];
int k;
bool ok(int u,int v){
    for(int i=2;i<=k;i++){
        if(id[i][u]<id[i][v])return false;
    }
    return true;
}
int main(){
    int n;
    cin>>n>>k;
    for(int j=1;j<=k;j++)
        for(int i=1;i<=n;i++){
            cin>>a[j][i];
            id[j][a[j][i]]=i;
        }
    for(int i=1;i<=n;i++){
        dp[i]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            if(ok(a[1][i],a[1][j]))dp[a[1][i]]=max(dp[a[1][i]],dp[a[1][j]]+1);
        }
    }
    cout<<*max_element(dp+1,dp+n+1)<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e3+50;
#define bug cout<<"hello"<<endl;
int a[6][maxn];
int id[6][maxn];
int dp[maxn];
int now[maxn];
int k;
bool ok(int u,int v){
    for(int i=1;i<=k;i++){
        if(id[i][u]>id[i][v])return false;
    }
    return true;
}
vector<int>ve[maxn];
int dfs(int u){
    if(dp[u]!=-1)return dp[u];
    int mx=0;
    for(int i=0;i<ve[u].size();i++){
        mx=max(mx,dfs(ve[u][i]));
    }
    return dp[u]=mx+1;
}
int main(){
    int n;
    cin>>n>>k;
    memset(dp,-1,sizeof(dp));
    for(int j=1;j<=k;j++)
        for(int i=1;i<=n;i++){
            cin>>a[j][i];
            id[j][a[j][i]]=i;
        }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if((i!=j)&&ok(i,j)){
                ve[i].push_back(j);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,dfs(i));
    }
    cout<<ans<<endl;
    return 0;

E - Caisa and Tree (暴力/素数筛选)

题意

给你一个树，让你求根（1）到一个点（v）之间路径上和v的值之间GCD不为1的且深度最大的点编号 有五十次修改一个点的操作

思路

看到50次修改就已经想到了暴力了。

但是还是想用正常操作做。

初始化每个值的素因子

首先我们对于每个点存一个他的素因子，然后在每次修改的时候重新建图。从根结点开始开一个栈，让遍历到的点进去，判断这个点的素因子是否出现在刚才遍历的路径中。然后选一个最大的。后把当前这个点也入栈。遍历这个点的儿子们。然后回溯的时候把所有的素因子中包括他的弹开。

//讲道理每个素因子开一个vector就可以了。可是一直过不去，其他人用map就过去了。。

第二种暴力解法。对于每个操作离线存起来，然后在修改的时候再把之间的询问一次性遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e6+50;
#define bug cout<<"hello"<<endl;
int n,q;
int a[maxn];
int prime[maxn];
bool check[maxn];
int cnt;

void init(int N){
    for(int i=2;i<=N;i++){
        if(!check[i]){
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt;j++){
            if(i*prime[j]>N)break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}
vector<int>ve[maxn];
void gao(int id,int val){
    ve[id].clear();
    for(int i=1;prime[i]*prime[i]<=val&&i<=cnt;i++){
        if(val%prime[i]==0){
            ve[id].push_back(prime[i]);
            while(val%prime[i]==0)val/=prime[i];
        }
    }
    if(val!=1)ve[id].push_back(val);
}
int Laxt[maxn],Next[maxn],To[maxn],res;

void add(int u,int v){
    Next[++res]=Laxt[u];Laxt[u]=res;To[res]=v;
}

int ans[maxn],dep[maxn];
map<int,vector<int> >mp;

void dfs(int u,int fa,int depp){
    ans[u]=-1,dep[u]=depp;
    for(int i=0;i<ve[u].size();i++){
        int v=ve[u][i];
        if(mp[v].size()==0){
            mp[v].push_back(u);
        }
        else{
            if(ans[u]==-1||dep[ans[u]]<dep[mp[v][mp[v].size()-1]])
                ans[u]=mp[v][mp[v].size()-1];
            mp[v].push_back(u);
        }
    }
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i];
        if(v==fa)continue;
        dfs(v,u,depp+1);
    }
    for(int i=0;i<ve[u].size();i++){
        int v=ve[u][i];
        mp[v].erase(mp[v].end()-1);
    }
}

int main(){
    init(2e6+10);
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),gao(i,a[i]);

    for(int i=1;i<n;i++){
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }

    dfs(1,-1,1);
    while(q--){
        int op,x,y;
        scanf("%d",&op);
        if(op==1){
            scanf("%d",&x);
            printf("%d\n",ans[x]);
        }
        else{
            scanf("%d%d",&x,&y);
            a[x]=y;
            gao(x,a[x]);
            dfs(1,-1,1);
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+50;
int Laxt[maxn],Next[maxn<<1],To[maxn<<1],cnt;

void add(int u,int v){
    Next[++cnt]=Laxt[u];Laxt[u]=cnt;To[cnt]=v;
}

int n,q;
int a[maxn];
int ans[maxn];
vector<int>Q[maxn];
vector<int>St;

void dfs(int u,int fa){
    int k=-1;
    if(!Q[u].empty()){
        for(int i=St.size()-1;i>=0;i--){
            int v=St[i];
            if(__gcd(a[u],a[v])!=1){
                k=v;break;
            }
        }
        for(int i=0;i<Q[u].size();i++)ans[Q[u][i]]=k;
        Q[u].clear();
    }
    St.push_back(u);
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i];
        if(v==fa)continue;
        dfs(v,u);
    }
    St.pop_back();
}

int main(){
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<n;i++){
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    int res=0;
    for(int i=1;i<=q;i++){
        int op,x,y;
        scanf("%d",&op);
        if(op==1){
            scanf("%d",&x);
            Q[x].push_back(i);
            res++;
        }
        else{
            if(res)dfs(1,-1);
            ans[i]=-10086;
            scanf("%d%d",&x,&y);
            a[x]=y;
            res=0;
        }
    }
    if(res)dfs(1,-1);
    for(int i=1;i<=q;i++)if(ans[i]!=-10086)printf("%d\n",ans[i]);
    return 0;
}