layout: post
title: Codeforces Round 264 (Div. 2)
author: "luowentaoaa"
catalog: true
tags:
mathjax: true
- codeforces
- DP
A - Caisa and Sugar （签到）
B - Caisa and Pylons （根据能量守恒定理hhh）
C - Gargari and Bishops （模拟）
题意
给出一个棋盘你可以放两个皇后，皇后可以攻击和他一个对角线的对象。但是两个皇后不能攻击到同一个目标 求出皇后攻击目标后获得的最大值
思路
首先对于对角线正对角线的x+y都是固定的，反对角线的X-Y都是固定的
然后我们就枚举对角线的值就行，
通过观察发现不相交的对角线他们的x+y的奇偶不同。所以我们分别求出最大即可
#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
",even+odd);
printf("%lld %lld %lld %lld
",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： 前半部分相同，后面改成每一个符合的关系一起建图。对于每个点求出一个最长路。
//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;
}
#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就过去了。。
第二种暴力解法。对于每个操作离线存起来，然后在修改的时候再把之间的询问一次性遍历。
#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
",ans[x]);
}
else{
scanf("%d%d",&x,&y);
a[x]=y;
gao(x,a[x]);
dfs(1,-1,1);
}
}
return 0;
}
#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
",ans[i]);
return 0;
}