2025-09-21 05:38:01ICPC 2019 徐州网络赛

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

#include

#include

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

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

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 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

#include

#include

using namespace std;

const int maxn = 100010;

unordered_map 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

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

{

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

{

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

{

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

{

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

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

#include

#include

#include

#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

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<

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

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

pam.count();

pam.dfs(0,0);

pam.dfs(1,0);

ll ans=0;

for(int i=2;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

#include

#include

#include

#include

using namespace std;

const int mod = 1e9+7;

const int maxn = 1000100;

typedef long long ll;

vector 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

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

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

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[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

#include

#include

#include

#include

using namespace std;

const int maxn = 100010;

typedef pair pii;

struct Point {

int x, y;

Point(int xx=0, int yy=0):x(xx), y(yy) {}

}p[1010];

set S;

int main() {

int n; scanf("%d", &n);

for(int i=0;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

for(int j=i+1;j

int now = 0;

for(int k=0;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

int now = 0;

for(int j=0;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

#include

#include

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<

}

if(ans)

cout<

else

puts("-1");

return 0;

}

（未完待补题。。。）