ICPC 2019 徐州网络赛
比赛时间：2019.9.7
比赛链接：The Preliminary Contest for ICPC Asia Xuzhou 2019
赛后的经验总结
// 比赛完才反应过来没看完全部题， J题树形dp没写太亏了。。。
// 几何旋律AK了，太强了Orz
// 虽然我们队A了8题，但如果时间分配好，认真读题避免看错题的话，应该至少多A一题
A. Who is better?
题意
两个人玩游戏，谁先消灭完敌人就赢。两条规则：1. 第一个人不能全部消灭完； 2. 后一次消灭的人数不超过前一次的两倍。
敌人人数通过 n 个同余方程求出。
非常明显的斐波那契博弈 + 中国剩余定理。
坑点
很裸的两个知识点强行结合在一起，于是愉快地抄起板子来，一交即WA，再交继续WA...
考虑到 CRT 计算过程中 ll 会溢出，改写 __int128，继续WA...
最后想起洛谷上测板子时候，把合并过程中的 a[i] >= m[i] 条件注释掉，然后就A了。。。
也就是说，测试数据认为余数比模数大也是合法的。
AC代码（新的 CRT 加强模板）
#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
typedef long long ll;
typedef __int128 i128;
const ll maxn = 1e15;
i128 exgcd(i128 a, i128 b, i128& x, i128& y) {
if(b==0) {
x = 1; y = 0;
return a;
}
i128 d = exgcd(b, a%b, y, x);
y -= (a/b) * x;
return d;
}
i128 a[20], m[20];
int n;
i128 excrt() {
if (n==1) {
if (m[0]>a[0]) return a[0];
else return -1;
}
i128 x, y, d;
for (int i=1;i<n;i++) {
d = exgcd(m[0], m[i], x, y);
if ((a[i]-a[0])%d!=0) return -1;
i128 t = m[i] / d;
x = ((a[i]-a[0]) / d * x % t + t) % t;
a[0] = x * m[0] + a[0];
m[0] = m[0] * m[i] / d;
a[0] = (a[0]%m[0] + m[0]) % m[0];
}
return a[0];
}
ll fib[100];
int main() {
cin>>n;
for(int i=0;i<n;i++) {
ll a1, a2;
cin>>a1>>a2;
m[i] = a1, a[i] = a2;
}
i128 x = excrt();
if(x<=1 || x>maxn) {
return 0 * printf("Tankernb!\n");
}
set<ll> S;
fib[1] = 1;
for(int i=2;i<100;i++) {
fib[i] = fib[i-1]+fib[i-2];
if(fib[i]>maxn) break;
S.insert(fib[i]);
}
if(S.find(x)==S.end())
printf("Zgxnb!\n");
else
printf("Lbnb!\n");
}
B. so easy
题意
有 n 个点从 1~n 编号，q 次操作 (z, x) 。（\(1 \le x < n <10^9\), \(1 \le q<10^6\))
z = 1 时，删除点 x；z = 2 时，查询从 x 之后能到达的第一个点（包括 x ）。
思路
n 的范围太大，线段树什么都存不了。
卡了很长时间，一直段错误。最后队友Yu用对查询离散化+并查集A了。
题解代码（使用 unordered_map）
#include<iostream>
#include<cstdio>
#include<unordered_map>
using namespace std;
const int maxn = 100010;
unordered_map<int, int> fa;
int findfa(int x) {
if(!fa.count(x)) return x;
return fa[x] = findfa(fa[x]);
}
int main() {
int n, q;
scanf("%d %d", &n, &q);
int op, x;
while(q--) {
scanf("%d %d", &op, &x);
if(op==1) {
fa[x] = findfa(x+1);
} else {
int ans = findfa(x);
if(ans>n) ans = -1;
printf("%d\n", ans);
}
}
return 0;
}
C. Buy Watermelon
题意
出题人的sb英语，三个人读完题都不知道写的什么。签到题WA了三次给强行怼过了。
大概题目想表达的是，要把西瓜分成重量都为偶数克的两部分吧。
思路
西瓜重量 w 必须为大于2的偶数。
AC代码
略。
D. Carneginon
队友Wu写的，据说是简单的KMP，也是签到题。
AC代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
char s[maxn],t[maxn];
int nexts[maxn],nextt[maxn];
void getnext_t(char *ptr){
int i,n,k;
n=strlen(ptr);
k=-1;
nextt[0]=-1;
i=0;
while(i<n)
{
if(k==-1 || ptr[i]==ptr[k])
{
i++;
k++;
nextt[i]=k;
}
else k=nextt[k];
}
}
void getnext_s(char *ptr){
int i,n,k;
n=strlen(ptr);
k=-1;
nexts[0]=-1;
i=0;
while(i<n)
{
if(k==-1 || ptr[i]==ptr[k])
{
i++;
k++;
nexts[i]=k;
}
else k=nexts[k];
}
}
int kmps(char *a,char *b)//匹配ab两串，a为父串
{
int i=0,j=0;
int len1=strlen(a);
int len2=strlen(b);
getnext_t(t);
while(i<len1&&j<len2)
{
if(j==-1||a[i]==b[j])
++i,++j;
else
j=nextt[j];
}
if(j==len2)
return i-j;
else
return -1;
}
int kmpt(char *a,char *b)//匹配ab两串，t为父串
{
int i=0,j=0;
int len1=strlen(a);
int len2=strlen(b);
while(i<len1&&j<len2)
{
if(j==-1||a[i]==b[j])
++i,++j;
else
j=nexts[j];
}
if(j==len2)
return i-j;
else
return -1;
}
bool cmp(char *a, char *b){
int len=strlen(s);
for(int i=0;i<len;i++) {
if(a[i]!=b[i]) return 0;
}return 1;
}
int main()
{
scanf("%s",s);
getnext_s(s);
int q;scanf("%d",&q);
for(int i=1;i<=q;i++){
scanf("%s",t);
int ls=strlen(s),lt=strlen(t);
if(ls==lt){
if(cmp(s,t)) printf("jntm!\n");
else printf("friend!\n");
}else if(ls>lt){
if(kmps(s,t)!=-1) printf("my child!\n");
else printf("oh, child!\n");
}else {
if(kmpt(t,s)!=-1) printf("my teacher!\n");
else printf("senior!\n");
}
}
return 0;
}
E. XKC's basketball team
题意
定义 w[i] 的 angry 值 为 w[i] 与右边最远的满足 w[j] >= w[i] + m 之间的人数。
求所有点的 angry 值之和。
思路
队友Yu写的，当时我沉浸在数论题中。。。
AC代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define inf 1000000000
using namespace std;
const int N = 5e5+10;
int tree[N<<4],num[N],cnt;
int ls[N<<4],rs[N<<4];
void update(int l,int r,int pos,int x,int d)
{
if(l==r)
{
tree[pos] = max(tree[pos],d);
return;
}
int mid = (l+r)>>1;
if(x<=mid)
{
if(ls[pos]==0)
ls[pos] = ++cnt;
update(l,mid,ls[pos],x,d);
}
else
{
if(rs[pos]==0)
rs[pos] = ++cnt;
update(mid+1,r,rs[pos],x,d);
}
tree[pos]=max(tree[ls[pos]],tree[rs[pos]]);
}
int qry(int l,int r,int L,int R,int pos)
{
if(L>R)return 0;
if(pos==0)return 0;
if(L<=l && r<=R)
return tree[pos];
int mid = (l+r)>>1;
int ret = 0;
if(L<=mid)
ret = max(ret,qry(l,mid,L,R,ls[pos]));
if(mid<R)
ret = max(ret,qry(mid+1,r,L,R,rs[pos]));
return ret;
}
int arr[N],hx[N];
int head;
int main()
{
cnt = 0;
int n,m;scanf("%d%d",&n,&m);
head = ++cnt;
for(int i=1;i<=n;++i)
{
scanf("%d",&arr[i]);
hx[i] = arr[i];
//update(1,inf,head,arr[i],i);
}
sort(hx+1,hx+1+n);
int len = unique(hx+1,hx+1+n)-hx-1;
for(int i=1;i<=n;++i)
{
int pos = lower_bound(hx+1,hx+1+len,arr[i])-hx;
update(1,len,head,pos,i);
}
bool ok = 1;
for(int i=1;i<=n;++i)
{
if(ok==0)
printf(" ");
ok=0;
int rs = arr[i]+m;
if(rs>hx[len])
printf("-1");
else
{
int pos = lower_bound(hx+1,hx+1+len,rs)-hx;
//cout<<endl<<i<<" "<<rs<<" "<<hx[pos]<<" "<<pos<<endl;
int ans = qry(1,len,pos,len,head);
if(ans<=i)
printf("-1");
else
printf("%d",ans-i-1);
}
}
puts("");
return 0;
}
G. Colorful String
题意
给定一个字符串，定义 value 为回文子串的不同字母个数，求它的全部回文子串的 value 之和。
思路
应该是字符串水题。
我用马拉车调了半天没弄出来。字符串队友那边用回文自动机直接一发A了。
AC代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+5;
const int N=26;
struct Palindromic_Tree
{
int next[maxn][N];
int fail[maxn];
int cnt[maxn];//第i个节点表示的回文串出现的次数，最后要调用count函数完成计算
int val[maxn];
int len[maxn];//节点i表示的回文串的长度
int S[maxn];//存放添加的字符
bool used[26];
int last;
int n;//字符数组指针
int p;//节点指针
int newnode(int l)
{
memset(next[p],0,sizeof next[p]);
cnt[p]=0;
len[p]=l;
return p++;
}
void init()
{
p=0;
newnode(0);
newnode(-1);
memset(used,0,sizeof used);
last=0;
n=0;
S[n]=-1;
fail[0]=1;
}
int get_fail(int x)
{
while(S[n-len[x]-1]!=S[n])
x=fail[x];
return x;
}
void add(int c)
{
c-='a';
S[++n]=c;
int cur=get_fail(last);
if(!next[cur][c])
{
int now=newnode(len[cur]+2);
fail[now]=next[get_fail(fail[cur])][c];
next[cur][c]=now;
}
last=next[cur][c];
cnt[last]++;
}
void count()
{
for(int i=p-1;i>=0;i--)
cnt[fail[i]]+=cnt[i];
}
void dfs(int now,ll num){
for(int i=0;i<26;i++) {
if(next[now][i]){
if(!used[i]) {
used[i]=1;
dfs(next[now][i],num+1);
used[i]=0;
}else dfs(next[now][i],num);
}
}
val[now]=num;
}
}pam;
char s[maxn];
int main()
{
scanf("%s",s);
pam.init();
int len=strlen(s);
for(int i=0;i<len;i++) pam.add(s[i]);
pam.count();
pam.dfs(0,0);
pam.dfs(1,0);
ll ans=0;
for(int i=2;i<pam.p;i++) ans+=1LL*pam.cnt[i]*pam.val[i];
printf("%lld\n",ans);
return 0;
}
J. Random Access Iterator （补）
题意
在树上按照图中 dfs 的方式，每次随机选一个儿子往下 dfs 得到树的深度。
求程序返回树的正确深度的概率。
思路
树形dp
比赛时候没有写，我的锅，全耗在数论题上了，结果全是通过数不超过100的难题。
注意题目程序的 dfs 每个节点跑了 k 次，相当于独立重复实验。
设tmp为节点 u 能达到根节点的概率， $tmp = \sum {1 \over k} dp[v] \(
\)dp[u] = 1 - (1-tmp)^k$
AC代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int mod = 1e9+7;
const int maxn = 1000100;
typedef long long ll;
vector<int> G[maxn];
ll dp[maxn], ans;
int dep[maxn], maxDep;
ll powmod(ll a, ll n) {
ll res = 1;
while(n) {
if(n&1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
void getDep(int u, int fa, int d) {
dep[u] = d;
maxDep = max(d, maxDep);
for(int i=0;i<G[u].size();i++) {
int v = G[u][i];
if(v!=fa) {
getDep(v, u, d+1);
}
}
}
void dfs(int u, int fa) {
if(dp[u]!=-1) return;
ll tmp = 0;
int son = G[u].size();
if(fa!=-1) --son;
for(int i=0;i<G[u].size();i++) {
int v = G[u][i];
if(v==fa) continue;
dfs(v, u);
tmp = (tmp + dp[v]*powmod(son, mod-2)%mod ) % mod;
}
dp[u] = (1-powmod((1-tmp+mod)%mod, son) + mod) % mod;
}
int main() {
int n; scanf("%d", &n);
for(int i=0;i<n-1;i++) {
int u, v;
scanf("%d %d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
getDep(1, -1, 1);
for(int i=1;i<=n;i++) {
if(dep[i]==maxDep)
dp[i] = 1;
else {
if(G[i].size()==1)
dp[i] = 0;
else
dp[i] = -1;
}
// cout<<dp[i]<<endl;
}
dp[1] = -1;
dfs(1, -1);
printf("%lld\n", dp[1]);
return 0;
}
K. Center
题意
给定平面上 n 个点，求加入最少的点使全部点能够中心对称。
思路
时限2s，复杂度O(n^3*logn)的暴力枚举算法勉强能过。
直接写完交一发，果然T了。
改用unordered_map存两点映射后的整数，降低了 logn 的复杂度，还是T了。
发现固定中心点的时候，剩下的点的对称点不会发生重合，直接检查是否插入新的点，带上 if(now>ans) break; 优化check过程，最后A了，几分钟之和才拿下A题。
AC代码（赛后改回了set可以A）
#include<iostream>
#include<cstdio>
#include<cmath>
#include<set>
#include<algorithm>
using namespace std;
const int maxn = 100010;
typedef pair<int, int> pii;
struct Point {
int x, y;
Point(int xx=0, int yy=0):x(xx), y(yy) {}
}p[1010];
set<pii> S;
int main() {
int n; scanf("%d", &n);
for(int i=0;i<n;i++) {
scanf("%d %d", &p[i].x, &p[i].y);
S.insert(make_pair(p[i].x, p[i].y));
}
int ans = n;
for(int i=0;i<n;i++) {
for(int j=i+1;j<n;j++) {
int now = 0;
for(int k=0;k<n;k++) {
if(S.find(make_pair(p[i].x+p[j].x-p[k].x, p[i].y+p[j].y-p[k].y))==S.end())
++now;
if(now>ans) break; // 没有会TLE
}
ans = min(ans, now);
}
}
for(int i=0;i<n;i++) {
int now = 0;
for(int j=0;j<n;j++) {
if(i==j) continue;
if(S.find(make_pair(2*p[i].x-p[j].x, 2*p[i].y-p[j].y))==S.end())
++now;
if(now>ans) break;
}
ans = min(ans, now);
}
printf("%d\n", ans);
return 0;
}
M. Longest subsequence
题意
给定两个字符串 s, t ，求 s 串中满足字典序大于 t 串的最长子序列长度。
思路
又是字符串，大概dp吧。
Wu读错题，让Yu白搞了快一个小时。。。
注意是子序列不是子串啊！！！
AC代码
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6+10;
char str[N];
int dp[N][30];
char ptn[N];
int main()
{
int n,m;scanf("%d%d",&n,&m);
scanf("%s%s",str+1,ptn+1);
m++;
ptn[m]='a'-1;
for(int i=0;i<26;++i)
dp[n][i]=n*2;
for(int i=n-1;i>=0;i--)
{
for(int j=0;j<26;++j)
dp[i][j] = dp[i+1][j];
dp[i][str[i+1]-'a'] = i+1;
}
int ans = 0;
int now = 0;
for(int i=1;i<=m && now<=n;++i)
{
for(int j=ptn[i]-'a'+1;j<26;++j)
if(dp[now][j]<=n)
ans = max(ans,n-dp[now][j]+i);
now = dp[now][ptn[i]-'a'];
//cout<<i<<" "<<ans<<" "<<now<<endl;
}
if(ans)
cout<<ans<<endl;
else
puts("-1");
return 0;
}
（未完待补题。。。）