Codeforces Round #264 (Div. 2)
【摘要】 Codeforces 463C Gargari and Bishops
做题感悟：
好不容易见到一场CF时间在15：30 比的就做了一下，第一题题意多了老半天没读懂 ，然后丢下第一题果断做第二题，第二题提议好理解，但是感觉太简单了，不敢相...
Codeforces 463C Gargari and Bishops
做题感悟：
好不容易见到一场CF时间在15：30 比的就做了一下，第一题题意多了老半天没读懂
，然后丢下第一题果断做第二题，第二题提议好理解，但是感觉太简单了，不敢相信，于是就抱着试一试的想法提交了一下预测通过，回头做第一题理解了题意提交预测通过，但是悲剧的是不一会就被hack 了 ，又看了代码才发现少了一种情况。第三题读懂题意后还没写完代码就结束比赛了，还好前两题最后都AC了。
解题思路：
在棋盘上放置两个象，象攻击的到的地方为象所在的方格的对角线，但是两个象不能攻击同一个格子且使所有攻击到的格子的和最大。这里要注意副对角线上 x + y 是递增 ，主对角线上处理一下也可以是递增的，这样两条对角线上的数都预处理出来了，这样就剩处理两个象不能同时攻击一个格子，这里只要分开坐标和（x+y）奇偶就可以，然后找到奇偶的最大值就可以了。
代码：
-
#include<iostream>
-
#include<cstring>
-
#include<cstdio>
-
#include<algorithm>
-
using namespace std ;
-
#define INT __int64
-
const int MX = 2000 + 10 ;
-
const int MY = 10000 + 10 ;
-
INT n ;
-
INT g[MX][MX] ,L[MY] ,R[MY] ;
-
void input()
-
{
-
memset(g ,0 ,sizeof(g)) ;
-
memset(L ,0 ,sizeof(L)) ;
-
memset(R ,0 ,sizeof(R)) ;
-
for(INT i = 1 ;i <= n ; ++i)
-
for(INT j = 1 ;j <= n ; ++j)
-
{
-
scanf("%I64d" ,&g[i][j]) ;
-
L[i+j] += g[i][j] ;
-
R[i-j+n*2+5] += g[i][j] ;
-
}
-
}
-
void solve()
-
{
-
INT MR = 0 ,ML = 0 ,ax = 1 ,ay = 1 ,bx = 1 ,by = 2 ;
-
for(INT i = 1 ;i <= n ; ++i)
-
for(INT j = 1 ;j <= n ; ++j)
-
if((i+j)%2)
-
{
-
if(L[i+j]+R[i-j+n*2+5]-g[i][j] > ML)
-
{
-
ML = L[i+j]+R[i-j+n*2+5]-g[i][j] ;
-
bx = i ;
-
by = j ;
-
}
-
}
-
else
-
{
-
if(L[i+j]+R[i-j+n*2+5]-g[i][j]>MR)
-
{
-
MR = L[i+j]+R[i-j+n*2+5]-g[i][j] ;
-
ax = i ;
-
ay = j ;
-
}
-
}
-
cout<<MR+ML<<endl ;
-
cout<<ax<<" "<<ay<<" "<<bx<<" "<<by<<endl ;
-
}
-
int main()
-
{
-
while(~scanf("%I64d" ,&n))
-
{
-
input() ;
-
solve() ;
-
}
-
return 0 ;
-
}
解题思路：因为 k 很小，如果在每个序列中 i 都在 j 前面我们就认为 i 到 j 有一条有向边，这样一处理，然后记忆话搜索一下就ok了。
代码：
-
#include<iostream>
-
#include<fstream>
-
#include<vector>
-
#include<sstream>
-
#include<cstring>
-
#include<cstdio>
-
#include<algorithm>
-
using namespace std ;
-
#define INT __int64
-
const int MX = 1000 + 10 ;
-
const int MY = 10000 + 10 ;
-
int n ,m ;
-
bool vis[MX][MX] ;
-
int g[10][MX] ,dp[MX] ;
-
void input()
-
{
-
int x ;
-
memset(g ,0 ,sizeof(g)) ;
-
memset(vis ,false ,sizeof(vis)) ;
-
for(int i = 0 ;i < m ; ++i)
-
for(int j = 1 ; j <= n ; ++j)
-
{
-
scanf("%d" ,&x) ;
-
g[i][x] = j ;
-
}
-
for(int i = 1 ;i <= n ; ++i)
-
{
-
vis[0][i] = true ;
-
for(int j = 1 ;j <= n ; ++j)
-
if(i != j)
-
{
-
bool flag = true ;
-
for(int k = 0 ;k < m ; ++k)
-
if(g[k][i] > g[k][j])
-
{
-
flag = false ;
-
break ;
-
}
-
vis[i][j] = flag ;
-
}
-
}
-
}
-
int DP_Memory(int x)
-
{
-
if(dp[x] != -1) return dp[x] ;
-
int& ans = dp[x] ;
-
ans = 0 ;
-
for(int i = 1 ;i <= n ; ++i)
-
if(vis[x][i])
-
ans = max(ans ,DP_Memory(i)) ;
-
ans++ ;
-
return ans ;
-
}
-
int main()
-
{
-
while(~scanf("%d%d" ,&n ,&m))
-
{
-
input() ;
-
memset(dp ,-1 ,sizeof(dp)) ;
-
cout<<DP_Memory(0)-1<<endl ;
-
}
-
return 0 ;
-
}
Codeforces 463E Caisa and Tree
做题感悟：比赛时根本就没看到这题，其实看到也做不出来，做题的时候应该发现突破点，就拿这题来说突破点是改变某个点的价值不会超过 50 次，同时发现应该加强自己的C++ 一些容器的运用。
解题思路：
上面已经说到本题的突破点是 50 ，so ~> 我们可以每次改变某个点的价值的时候重新预处理一下 ，这样最多预处理 50 次。那么接下来就解决怎样预处理的问题了，这里因为第一问求的是每个点距离此点最近的且最大公约数大于 1 的节点 ，所以我们可以分解素数，把每一个节点的 value 都分解了，DFS找一个深度最深的且与当前节点有公共素因子的节点 就可以了。
代码：
-
#include<iostream>
-
#include<sstream>
-
#include<map>
-
#include<cmath>
-
#include<fstream>
-
#include<vector>
-
#include<sstream>
-
#include<cstring>
-
#include<cstdio>
-
#include<conio.h>
-
#include<stack>
-
#include<bitset>
-
#include<ctime>
-
#include<cstring>
-
#include<algorithm>
-
using namespace std ;
-
#define INT __int64
-
const int MP = 2000000 + 5 ;
-
const int MY = 150000 + 5 ;
-
const int MX = 100000 + 5 ;
-
int n ,m ;
-
bool isprime[MP] ;
-
int pos[MP] ,prime[MY] ,value[MX] ,ans[MX] ,niv[MX] ;
-
vector<int> G[MX] ;
-
stack<int> s[MY] ;
-
void InitPrime() // 筛选素数
-
{
-
int num = 0 ;
-
memset(isprime ,false ,sizeof(isprime)) ;
-
for(int i = 2 ;i < MP ; ++i)
-
{
-
if(!isprime[i])
-
{
-
prime[++num] = i ;
-
pos[i] = num ;
-
}
-
for(int j = 1 ;j <= num && prime[j]*i < MP-5 ; ++j)
-
{
-
isprime[i*prime[j]] = true ;
-
if(i % prime[j] == 0)
-
break ;
-
}
-
}
-
}
-
void input()
-
{
-
int x ,y ;
-
for(int i = 1 ;i <= n ; ++i)
-
{
-
scanf("%d" ,&value[i]) ;
-
G[i].clear() ;
-
}
-
for(int i = 1 ;i < n ; ++i)
-
{
-
scanf("%d%d" ,&x ,&y) ;
-
G[x].push_back(y) ;
-
G[y].push_back(x) ;
-
}
-
}
-
void DFS(int node ,int father)
-
{
-
vector<int> v ;
-
int x = value[node] ;
-
int d = 2 ,step = 1 ;
-
ans[node] = 0 ;
-
while(d*d <= x)
-
{
-
if(!(x%d))
-
{
-
if(!s[pos[d]].empty())
-
{
-
int y = s[pos[d]].top() ;
-
if(niv[y] > niv[ans[node]])
-
ans[node] = y ;
-
}
-
v.push_back(pos[d]) ;
-
s[pos[d]].push(node) ;
-
while(x%d == 0)
-
{
-
x /= d ;
-
}
-
}
-
++step ;
-
d = prime[step] ;
-
}
-
if(x > 1)
-
{
-
if(!s[pos[x]].empty())
-
{
-
int y = s[pos[x]].top() ;
-
if(niv[y] > niv[ans[node]])
-
ans[node] = y ;
-
}
-
v.push_back(pos[x]) ;
-
s[pos[x]].push(node) ;
-
}
-
for(int i = 0 ; i < G[node].size() ; ++i)
-
if(G[node][i] != father)
-
{
-
int y = G[node][i] ;
-
niv[y] = niv[node] + 1 ;
-
DFS(y , node) ;
-
}
-
for(int i = 0 ;i < v.size() ; ++i)
-
s[v[i]].pop() ;
-
v.clear() ;
-
}
-
int main()
-
{
-
int p ,x ,w ;
-
InitPrime() ;
-
while(~scanf("%d%d" ,&n ,&m))
-
{
-
input() ;
-
niv[1] = 1 ;
-
DFS(1 ,-1) ;
-
while(m--)
-
{
-
scanf("%d%d" ,&p ,&x) ;
-
if(p == 1)
-
cout<<(ans[x] > 0 ? ans[x] : -1)<<endl ;
-
else
-
{
-
scanf("%d" ,&w) ;
-
value[x] = w ;
-
DFS(1 ,-1) ;
-
}
-
}
-
}
-
return 0 ;
-
}
文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nyist_zxp/article/details/38958505
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）