2019CCPC秦皇岛部分简要题解A - Angle BeatsD - DecimalE - EscapeF - Forest ProgramI - InvokerJ - MUV LUV EXTRA K - MUV LUV UNLIMITED

50 阅读 0 评论 33 点赞

我是靠谱客的博主鲜艳便当，最近开发中收集的这篇文章主要介绍2019CCPC秦皇岛部分简要题解A - Angle BeatsD - DecimalE - EscapeF - Forest ProgramI - InvokerJ - MUV LUV EXTRA K - MUV LUV UNLIMITED，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A - Angle Beats

对于每个询问 $a_i$ ，枚举 $p_u$ ，分别以 $a_i$ 和 $p_u$ 为直角点计数即可。注意去重。

这题主要是卡常，需要使用 $unsigned;int$ 进行 $hash$ 。

#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define sz(x)
(int)x.size()
#define cl(x)
x.clear()
#define all(x)
x.begin() , x.end()
#define rep(i , x , n)
for(int i = x ; i <= n ; i ++)
#define per(i , n , x)
for(int i = n ; i >= x ; i --)
#define mem0(x)
memset(x , 0 , sizeof(x))
#define mem_1(x)
memset(x , -1 , sizeof(x))
#define mem_inf(x)
memset(x , 0x3f , sizeof(x))
#define debug(x)
cerr << #x << " = " << x << 'n'
#define ddebug(x , y)
cerr << #x << " = " << x << "
" << #y << " = " << y << 'n'
#define ios std::ios::sync_with_stdio(false) , cin.tie(0)
using namespace std ;
typedef long long ll ;
typedef long double ld ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
typedef unsigned long long ull ;
typedef double db ;
const int mod = 998244353 ;
const int maxn = 2e3 + 10 ;
const int inf = 0x3f3f3f3f ;
const double eps = 1e-6 ;
int n , q ;
int x[maxn] , y[maxn] ;
unordered_map<unsigned , int> cnt[maxn] ;
unordered_map<unsigned , int> mp ;
unsigned cal(int a , int b)
{
int d = __gcd(a , b) ;
a /= d ;
b /= d ;
if(a < 0)
a = -a , b = -b ;
else if(a == 0)
b = abs(b) ;
return (unsigned)a * 217636919 + (unsigned)b * 51646229 ;
}
void mark(int i , int a , int b)
{
cnt[i][cal(a , b)] ++ ;
}
int main()
{
ios ;
cin >> n >> q ;
rep(i , 1 , n)
cin >> x[i] >> y[i] ;
rep(i , 1 , n)
rep(j , 1 , n)
if(i != j)
mark(i , x[i] - x[j] , y[i] - y[j]) ;
while(q --)
{
int a , b ;
cin >> a >> b ;
ll ans = 0 ;
ll sum = 0 ;
cl(mp) ;
rep(i , 1 , n)
{
int X = a - x[i] ;
int Y = b - y[i] ;
mp[cal(X , Y)] ++ ;
}
rep(i , 1 , n)
{
ll X = a - x[i] ;
ll Y = b - y[i] ;
ans += cnt[i][cal(Y , -X)] ;
sum += mp[cal(Y , -X)] ;
}
cout << ans + sum / 2 << 'n' ;
}
return 0 ;
}

D - Decimal

有限小数等价于 $dpi{150}n$ 的因子只能包含 $2$ 和 $5$ 。

#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define sz(x)
(int)x.size()
#define cl(x)
x.clear()
#define all(x)
x.begin() , x.end()
#define rep(i , x , n)
for(int i = x ; i <= n ; i ++)
#define per(i , n , x)
for(int i = n ; i >= x ; i --)
#define mem0(x)
memset(x , 0 , sizeof(x))
#define mem_1(x)
memset(x , -1 , sizeof(x))
#define mem_inf(x)
memset(x , 0x3f , sizeof(x))
#define debug(x)
cerr << #x << " = " << x << 'n'
#define ddebug(x , y)
cerr << #x << " = " << x << "
" << #y << " = " << y << 'n'
#define ios std::ios::sync_with_stdio(false) , cin.tie(0)
using namespace std ;
typedef long long ll ;
typedef long double ld ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
typedef double db ;
const int mod = 998244353 ;
const int maxn = 2e5 + 10 ;
const int inf = 0x3f3f3f3f ;
const double eps = 1e-6 ;
int main()
{
ios ;
int T ;
cin >> T ;
while(T --)
{
int n ;
cin >> n ;
while(n % 2 == 0)
n /= 2 ;
while(n % 5 == 0)
n /= 5 ;
if(n > 1)
cout << "Yesn" ;
else
cout << "Non" ;
}
return 0 ;
}

E - Escape

如果一个格子放了装置，那只能经过一个机器人。

如果一个格子不放装置，竖直方向和水平方向各自可以经过一个机器人。

每个点拆成一个竖直点和一个水平点。格子内部竖直点和水平点连边代表转向。水平方向相邻的水平点连边，代表直行。竖直方向相邻的竖直点连边，代表直行。

卡 $isap$ ，用 $dinic$ 。

#include<bits/stdc++.h>
using namespace std ;
const int mod = 998244353 ;
const int maxn = 1e6 + 10 ;
const int inf = 0x3f3f3f3f ;
struct Dinic
{
int tot ;
int Next[maxn],last[maxn],to[maxn],flow[maxn],q[maxn],dis[maxn],S,T;
void init()
{
tot = 1 ;
memset(last , 0 , sizeof(last)) ;
}
void add(int x,int y,int v) {
Next[++tot]=last[x]; last[x]=tot; to[tot]=y; flow[tot]=v;
}
void auto_add(int x,int y,int w) {
add(x,y,w);
add(y,x,0);
}
bool bfs() {
int l=0,r=1; q[1]=S;
for (int i=1;i<=T;i++) dis[i]=0;
dis[S]=1;
while (l<r) {
int k=q[++l];
for (int i=last[k];i;i=Next[i]) {
if (dis[to[i]]||!flow[i]) continue;
dis[q[++r]=to[i]]=dis[k]+1;
}
}
return dis[T]>0;
}
int dfs(int x,int y) {
if (!y) return 0;
if (x==T) return y;
int sum=0;
for (int i=last[x];i;i=Next[i]) {
if (dis[to[i]]!=dis[x]+1||!flow[i]) continue;
int tmp=dfs(to[i],min(y-sum,flow[i]));
if (tmp) {
sum+=tmp;
flow[i]-=tmp;
flow[i^1]+=tmp;
}
else dis[to[i]]=0;
if (sum==y) return sum;
}
return sum;
}
int dinic() {
int ans=0;
while (bfs()) ans+=dfs(S,inf);
return ans;
}
} dinic ;
int main()
{
std::ios::sync_with_stdio(false) ;
std::cin.tie(0) ;
int T ;
cin >> T ;
while(T --)
{
int n , m , a , b ;
cin >> n >> m >> a >> b ;
vector<string> s(n) ;
for(int i = 0 ; i < n ; i ++)
cin >> s[i] ;
vector<int> x0(a) ;
vector<int> x1(b) ;
for(int i = 0 ; i < a ; i ++)
cin >> x0[i] ;
for(int i = 0 ; i < b ; i ++)
cin >> x1[i] ;
dinic.init() ;
dinic.S = n * m * 2 + a + b + 1 ;
dinic.T = n * m * 2 + a + b + 2 ;
function<int(int , int)> v = [&](int x , int y)
{
return (x - 1) * m + y ;
} ;
function<int(int , int)> h = [&](int x , int y)
{
return n * m + (x - 1) * m + y ;
} ;
for(int i = 0 ; i < a ; i ++)
{
dinic.auto_add(dinic.S , n * m * 2 + i + 1 , 1) ;
if(s[0][x0[i] - 1] == '0')
dinic.auto_add(n * m * 2 + i + 1 , v(1 , x0[i]) , 1) ;
}
for(int i = 0 ; i < b ; i ++)
{
dinic.auto_add(n * m * 2 + a + i + 1 , dinic.T , 1) ;
if(s[n - 1][x1[i] - 1] == '0')
dinic.auto_add(v(n , x1[i]) , n * m * 2 + a + i + 1 , 1) ;
}
vector<int> row = {-1 , 1 , 0 , 0} ;
vector<int> col = {0 , 0 , -1 , 1} ;
for(int i = 0 ; i < n ; i ++)
for(int j = 0 ; j < m ; j ++)
{
if(s[i][j] == '1')
continue ;
dinic.auto_add(v(i + 1 , j + 1) , h(i + 1 , j + 1) , 1) ;
dinic.auto_add(h(i + 1 , j + 1) , v(i + 1 , j + 1) , 1) ;
for(int k = 0 ; k < 4 ; k ++)
{
int nx = i + row[k] ;
int ny = j + col[k] ;
if(nx < 0 || nx >= n || ny < 0 || ny >= m || s[nx][ny] == '1')
continue ;
if(k < 2)
dinic.auto_add(v(i + 1 , j + 1) , v(nx + 1 , ny + 1) , 1) ;
else
dinic.auto_add(h(i + 1 , j + 1) , h(nx + 1 , ny + 1) , 1) ;
}
}
int cnt = dinic.dinic() ;
if(cnt == a)
cout << "Yesn" ;
else
cout << "Non" ;
}
return 0 ;
}

F - Forest Program

答案是 $2^xtimes prod (2^{k_i}-1)$ 。其中 $x$ 表示不在环上的边的个数， $k_i$ 表示简单环的大小。

$vis[i]=0$ 表示 $i$ 未访问。

$vis[i]=1$ 表示 $i$ 已访问。

$vis[i]=-1$ 表示 $i$ 及其 $dfs$ 子树已访问完毕。

跑一遍 $dfs$ ，打好标记，即可得出环的大小。

#include<bits/stdc++.h>
using namespace std ;
const int mod = 998244353 ;
int main()
{
std::ios::sync_with_stdio(false) ;
std::cin.tie(0) ;
int n , m ;
cin >> n >> m ;
vector<vector<int>> g(n + 1) ;
for(int i = 0 ; i < m ; i ++)
{
int u , v ;
cin >> u >> v ;
g[u].push_back(v) ;
g[v].push_back(u) ;
}
vector<int> vis(n + 1 , 0) ;
vector<int> fa(n + 1 , 0) ;
function<long long(long long , long long)> qpow = [&](long long a , long long b)
{
long long res = a ;
long long ans = 1 ;
while(b > 0)
{
if(b & 1)
ans *= res , ans %= mod ;
res *= res ;
res %= mod ;
b >>= 1 ;
}
return ans ;
} ;
function<long long(int , int)> cal = [&](int anc , int now)
{
int num = 1 ;
while(now != anc)
{
now = fa[now] ;
num ++ ;
//cout << "!11n" ;
}
m -= num ;
return num ;
} ;
long long ans = 1 ;
function<void(int)> dfs = [&](int u)
{
for(auto v : g[u])
{
if(fa[u] == v)
continue ;
if(fa[v] == 0)
fa[v] = u , dfs(v) ;
else if(fa[v] != -1) ans *= qpow(2 , cal(v , u)) - 1 , ans %= mod ;
}
fa[u] = -1 ;
} ;
for(int i = 1 ; i <= n ; i ++)
if(vis[i] == 0)
dfs(i) ;
ans *= qpow(2 , m) , ans %= mod ;
ans = (ans + mod) % mod ;
cout << ans << 'n' ;
return 0 ;
}

I - Invoker

每个技能最多有 $6$ 种排列。

$dp[i][j]$ 表示前 $i$ 个技能已经使用过且第 $i$ 个技能使用的是第 $j$ 个排列的最小代价。暴力转移。预处理细心即可。

#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define sz(x)
(int)x.size()
#define cl(x)
x.clear()
#define all(x)
x.begin() , x.end()
#define rep(i , x , n)
for(int i = x ; i <= n ; i ++)
#define per(i , n , x)
for(int i = n ; i >= x ; i --)
#define mem0(x)
memset(x , 0 , sizeof(x))
#define mem_1(x)
memset(x , -1 , sizeof(x))
#define mem_inf(x)
memset(x , 0x3f , sizeof(x))
#define debug(x)
cerr << #x << " = " << x << 'n'
#define ddebug(x , y)
cerr << #x << " = " << x << "
" << #y << " = " << y << 'n'
#define ios std::ios::sync_with_stdio(false) , cin.tie(0)
using namespace std ;
typedef long long ll ;
typedef long double ld ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
typedef double db ;
const int mod = 998244353 ;
const int maxn = 1e5 + 10 ;
const int inf = 0x3f3f3f3f ;
const double eps = 1e-6 ;
map<string , string> id ;
map<string , vector<string> > mp ;
char c[maxn] ;
int now = 0 ;
int dp[maxn][15] ;
int p[5] ;
void init()
{
id["Y"] = "QQQ" ;
id["V"] = "QQW" ;
id["G"] = "QQE" ;
id["C"] = "WWW" ;
id["X"] = "QWW" ;
id["Z"] = "WWE" ;
id["T"] = "EEE" ;
id["F"] = "QEE" ;
id["D"] = "WEE" ;
id["B"] = "QWE" ;
for(auto u : id)
{
vector<string> v ;
string id1 = u.fi ;
string id2 = u.se ;
rep(i , 0 , 2)
p[i] = i ;
do
{
string t = "" ;
rep(i , 0 , 2)
t += id2[p[i]] ;
v.pb(t) ;
}
while(next_permutation(p , p + 3)) ;
mp[id1] = v ;
}
}
int change(string t1 , string t2)
{
if(t1[0] == t2[0] && t1[1] == t2[1] && t1[2] == t2[2])
return 0 ;
else if(t1[1] == t2[0] && t1[2] == t2[1])
return 1 ;
else if(t1[2] == t2[0])
return 2 ;
else
return 3 ;
}
int main()
{
ios ;
string s ;
cin >> s ;
int len = sz(s) ;
init() ;
mem_inf(dp) ;
rep(i , 0 , 5)
dp[0][i] = 3 ;
rep(i , 1 , len - 1)
rep(j , 0 , 5)
rep(k , 0 , 5)
{
string t1 = "" ;
t1 += s[i - 1] ;
string t2 = "" ;
t2 += s[i] ;
dp[i][j] = min(dp[i][j] , dp[i - 1][k] + change(mp[t1][k] , mp[t2][j])) ;
}
int ans = inf ;
rep(i , 0 , 5)
ans = min(ans , dp[len - 1][i]) ;
cout << ans + len << 'n' ;
return 0 ;
}

J - MUV LUV EXTRA

反转字符串后用kmp对长度为p前缀询问最小周期l，答案是a*p-b*l的最大值。注意ans的初值设置为负无穷，因为答案可能是负数。

#include<bits/stdc++.h>
using namespace std ;
int main()
{
std::ios::sync_with_stdio(false) ;
std::cin.tie(0) ;
long long a , b ;
string s ;
cin >> a >> b ;
cin >> s ;
int len = s.size() ;
reverse(s.begin() , s.end()) ;
vector<int> nxt(len + 1) ;
nxt[0] = -1 ;
int j = 0 , k = -1 ;
while(j < len)
{
if(k == -1 || s[j] == s[k])
j ++ , k ++ , nxt[j] = k ;
else
k = nxt[k] ;
}
long long ans = -1e18 ;
for(int i = 0 ; i < len ; i ++)
{
if(s[i] == '.')
break ;
long long p = i + 1 ;
long long l = (i + 1) - nxt[(i + 1)] ;
ans = max(ans , a * p - b * l) ;
}
cout << ans << 'n' ;
return 0 ;
}

K - MUV LUV UNLIMITED

一、如果树是一条链，直接按照长度的奇偶性判断即可。

二、如果树不是一条链。

定义叶子到分叉点的链是枝条。枝条不包括分叉点。

（1）如果存在长度是1的枝条，那么先手必胜。如果把长度是1的枝条的叶子节点去掉，那么到达先手必败态，那把必败态丢给对方，自己就赢了。如果把长度是1的枝条的叶子节点去掉，那么到达先手必胜态，那我就把必胜态的那一步删除的叶子节点在当前步就删除掉，还是把必败态丢给对方，自己还是赢了。

（2）如果枝条长度都是偶数，那么先手必败。因为后手可以复制先手的策略，使先手操作后产生长度是1的枝条，从而使后手获胜。

#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define sz(x)
(int)x.size()
#define cl(x)
x.clear()
#define all(x)
x.begin() , x.end()
#define rep(i , x , n)
for(int i = x ; i <= n ; i ++)
#define per(i , n , x)
for(int i = n ; i >= x ; i --)
#define mem0(x)
memset(x , 0 , sizeof(x))
#define mem_1(x)
memset(x , -1 , sizeof(x))
#define mem_inf(x)
memset(x , 0x3f , sizeof(x))
#define debug(x)
cerr << #x << " = " << x << 'n'
#define ddebug(x , y)
cerr << #x << " = " << x << "
" << #y << " = " << y << 'n'
#define ios std::ios::sync_with_stdio(false) , cin.tie(0)
using namespace std ;
typedef long long ll ;
typedef long double ld ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
typedef double db ;
const int mod = 998244353 ;
const int maxn = 1e6 + 10 ;
const int inf = 0x3f3f3f3f ;
const double eps = 1e-6 ;
int n ;
vector<int> g[maxn] ;
int dep[maxn] ;
int p[maxn] ;
void dfs(int u)
{
for(auto v : g[u])
dep[v] = dep[u] + 1 , dfs(v) ;
}
int main()
{
ios ;
int T ;
cin >> T ;
while(T --)
{
cin >> n ;
rep(i , 1 , n)
cl(g[i]) ;
rep(i , 2 , n)
{
cin >> p[i] ;
g[p[i]].pb(i) ;
}
dfs(1) ;
int mx = 0 ;
rep(i , 2 , n)
mx = max(mx , dep[i]) ;
if(mx == n - 1)
{
if(n % 2 == 1)
cout << "Takerun" ;
else
cout << "Meiyan" ;
}
else
{
bool flag = 0 ;
rep(i , 1 , n)
if(sz(g[i]) == 0)
{
int len = 0 ;
int now = i ;
while(sz(g[now]) <= 1)
{
len ++ ;
now = p[now] ;
}
if(len % 2 == 1)
{
flag = 1 ;
break ;
}
}
if(flag)
cout << "Takerun" ;
else
cout << "Meiyan" ;
}
}
return 0 ;
}