526互联

The 2019 ICPC Asia Yinchuan Regional Contest

发布时间 2023-11-19 15:59:09作者: 空気力学の詩

Preface

好久没有一场比赛做出两位数以上的题了，评价是写代码写得好爽

感觉这种时间比较古早的场的拿奖难度和现在比起来低好多的说，这场在现场如果有10题都能捧个亚军的杯了

但感觉主要是我们J题最后5分钟乱搞了个做法过了样例交上去就直接过了，后面看了其它人的做法好像和我们的都不一样的说，不知道是数据水骗过去了还是真的另辟蹊径了

A. Girls Band Party

很trivial的一个题，不难发现因为对于一个名字的卡中至多只能选一张，同时加成的种类只有\(0\%\sim 150\%\)共16种

因此可以直接大力DP，设\(f_{i,j,k}\)表示处理了前\(i\)种卡牌，选了其中的\(j\)张，并且此时的加成为\(k\times 10\%\)时得到的power之和的最大值

复杂度显然就是\(O(5\times 16\times n)\)，可以通过此题

#include<cstdio>
#include<iostream>
#include<string>
#include<map>
#include<utility>
#include<vector>
#include<set>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,INF=1e9;
int t,n,f[2][6][16];
int main()
{
	//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
	ios::sync_with_stdio(false); cin.tie(0);
	for (cin>>t;t;--t)
	{
		map <string,vector <pair <string,int>>> cards;
		RI i,j; for (cin>>n,i=1;i<=n;++i)
		{
			string name,col; int power; cin>>name>>col>>power;
			cards[name].push_back(make_pair(col,power));
		}
		set <string> sp_name; string sp_col;
		for (i=1;i<=5;++i)
		{
			string name; cin>>name; sp_name.insert(name);
		}
		cin>>sp_col; int now=1,lst=0;
		for (i=0;i<6;++i) for (j=0;j<16;++j) f[lst][i][j]=-INF; f[lst][0][0]=0;
		for (auto [name,vec]:cards)
		{
			for (i=0;i<6;++i) for (j=0;j<16;++j) f[now][i][j]=-INF;
			int coef=sp_name.count(name)?1:0;
			for (i=0;i<6;++i) for (j=0;j<16;++j)
			{
				if (f[lst][i][j]==-INF) continue;
				f[now][i][j]=max(f[now][i][j],f[lst][i][j]);
				if (i==5) continue;
				for (auto [col,power]:vec)
				{
					int ncoef=coef+(col==sp_col?2:0);
					f[now][i+1][j+ncoef]=max(f[now][i+1][j+ncoef],f[lst][i][j]+power);
				}
			}
			now^=1; lst^=1;
		}
		int ans=0; for (i=0;i<16;++i) if (f[lst][5][i]!=-INF)
		ans=max(ans,(int)((1.0+0.1*i)*f[lst][5][i]));
		printf("%d\n",ans);
	}
	return 0;
}

B. So Easy

签到题，假设\(a_{x_0,y_0}=-1\)，随便找一个\(x,y\)满足\(x\ne x_0,y\ne y_0\)，则可以发现\(a_{x_0,y_0}=a_{x,y_0}+a_{x_0,y}-a_{x,y}\)

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
int n,a[N][N];
int main()
{
	//freopen("B.in","r",stdin); freopen("B.out","w",stdout);
	RI i,j; int x,y,x0,y0; for (scanf("%d",&n),i=1;i<=n;++i)
	for (j=1;j<=n;++j) if (scanf("%d",&a[i][j]),a[i][j]==-1) x0=i,y0=j;
	for (i=1;i<=n;++i) for (j=1;j<=n;++j)
	if (a[i][j]!=-1&&i!=x0&&j!=y0) x=i,y=j;
	return printf("%d",a[x][y0]+a[x0][y]-a[x][y]),0;
}

C. Image Processing

防AK题，感觉是昨天打的2020银川的B的超级加强版

D. Easy Problem

有手就行的反演题，但出题人不知道怎么想的搞了个抽象模数就很恶心人

经过最基本的莫反变换我们得到答案的表达式为：

\[\sum_{i=1}^{\lfloor\frac{m}{d}\rfloor} \mu(i)\times (\sum_{di|j} j^k)^n \]

注意到模数不是质数，因此我们要用扩展欧拉定理对指数上的\(n\)降幂，因此还要讨论下\(n\)和\(\phi(59964251)\)的大小关系

总复杂度\(O(m\log^2 m)\)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,mod=59964251,pmod=59870352;
int t,n,m,d,k,pri[N],vis[N],cnt,mu[N]; char s[N];
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
inline void dec(int& x,CI y)
{
	if ((x-=y)<0) x+=mod;
}
inline int quick_pow(int x,int p,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
	RI i,j; for (mu[1]=1,i=2;i<=n;++i)
	{
		if (!vis[i]) pri[++cnt]=i,mu[i]=-1;
		for (j=1;j<=cnt&&i*pri[j]<=n;++j)
		if (vis[i*pri[j]]=1,i%pri[j]) mu[i*pri[j]]=-mu[i]; else break;
	}
}
int main()
{
	//freopen("D.in","r",stdin); freopen("D.out","w",stdout);
	for (scanf("%d",&t),init(100000);t;--t)
	{
		scanf("%s%d%d%d",s+1,&m,&d,&k); n=strlen(s+1);
		RI i,j; int g=0,ans=0;
		if (n<=8)
		{
			for (i=1;i<=n;++i) g=g*10+s[i]-'0';
			if (g>=pmod) g=g%pmod+pmod;
		} else
		{
			for (i=1;i<=n;++i) g=(g*10+s[i]-'0')%pmod; g=g%pmod+pmod;
		}
		for (i=1;i*d<=m;++i) if (mu[i])
		{
			int ret=0,base=i*d;
			for (j=base;j<=m;j+=base) inc(ret,quick_pow(j,k));
			if (mu[i]==1) inc(ans,quick_pow(ret,g)); else dec(ans,quick_pow(ret,g));
		}
		printf("%d\n",ans);
	}
	return 0;
}

E. XOR Tree

做不来一点，根本没想到题解第一步的那个转化，然后直接寄了

但后面的DP部分题解讲的贼简略连方程都不给，直接弃疗不管了

F. Function!

题目都没仔细看就被祁神秒了

这题的要点大概就是要注意到后面的\(\lceil f_{b}^{-1}\left( a \right) \rceil\)始终为\(1\)，而\(\log_a b\)的值在\(a>\sqrt n\)时又恒为\(1\)，就可以暴力处理了

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int BLK=1e6+10;
const int MOD=998244353;
const int inv2=499122177;
const int inv6=166374059;

int sqr(int n){n%=MOD; return n*(n+1)%MOD*(2*n+1)%MOD*inv6%MOD;}

int powe(int x, int p){
	int res=1;
	while (p>0){ if (p&1) res=res*x%MOD; x=x*x%MOD; p>>=1;}
	return res;	
}
signed main(){
//	printf("%lld\n", powe(6, MOD-2));
	int n; scanf("%lld", &n);
	int blk1=min(BLK, n);
	int ans=0;
		//printf("%lld\n", blk1);
	for (int a=2; a<=blk1; ++a){
		int cur=1;
		int powe=a;
		int res=0;
		while (1){
		//	printf("a=%lld cur=%lld powe=%lld\n", a, cur, powe);
			res = (res+cur*(min(n+1, a*powe)-powe)%MOD)%MOD;
			if (a*powe>n) break;
			powe = a*powe;
			++cur;
		}
		ans = (ans + res*a%MOD)%MOD;
	}     
	if (n>BLK){
//		for (int a=BLK+1; a<=n; ++a) ans=(ans+(n+1-a)*a%MOD)%MOD;	
		int tmp = (BLK+1+n)%MOD*((n-BLK)%MOD)%MOD*((n+1)%MOD)%MOD*inv2%MOD;
		tmp = ((tmp - sqr(n) +  MOD)%MOD + sqr(BLK))%MOD;
		ans = (ans+tmp)%MOD;
	}
	printf("%lld\n", ans);
	return 0;	
}

G. Pot!!

不难发现有用的质数只有\(\{2,3,5,7\}\)，因此直接对每个搞个线段树维护下即可

#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,pri[4]={2,3,5,7};
struct ifo
{
	int d[4];
	inline ifo(void) { memset(d,0,sizeof(d)); }
	friend inline ifo operator + (const ifo& A,const ifo& B)
	{
		ifo C; for (RI i=0;i<4;++i) C.d[i]=max(A.d[i],B.d[i]); return C;
	}
	friend inline ifo operator ^ (const ifo& A,const ifo& B)
	{
		ifo C; for (RI i=0;i<4;++i) C.d[i]=A.d[i]+B.d[i]; return C;
	}
}; int n,q,l,r,x; char opt[20];
class Segment_Tree
{
	private:
		ifo t[N<<2],tag[N<<2]; int vis[N<<2];
	public:
		#define TN CI now=1,CI l=1,CI r=n
		#define LS now<<1,l,mid
		#define RS now<<1|1,mid+1,r
		inline void apply(CI now,const ifo& it)
		{
			vis[now]=1; tag[now]=tag[now]^it; t[now]=t[now]^it;
		}
		inline void pushup(CI now)
		{
			t[now]=t[now<<1]+t[now<<1|1];
		}
		inline void pushdown(CI now)
		{
			if (vis[now]) apply(now<<1,tag[now]),apply(now<<1|1,tag[now]),tag[now]=ifo(),vis[now]=0;
		}
		inline void modify(CI beg,CI end,const ifo& it,TN)
		{
			if (beg<=l&&r<=end) return apply(now,it); int mid=l+r>>1; pushdown(now);
			if (beg<=mid) modify(beg,end,it,LS); if (end>mid) modify(beg,end,it,RS); pushup(now);
		}
		inline ifo query(CI beg,CI end,TN)
		{
			if (beg<=l&&r<=end) return t[now]; int mid=l+r>>1; ifo ret; pushdown(now);
			if (beg<=mid) ret=ret+query(beg,end,LS); if (end>mid) ret=ret+query(beg,end,RS); return ret;
		}
		#undef TN
		#undef LS
		#undef RS
}SEG;
int main()
{
//	freopen("G.in","r",stdin); freopen("G.out","w",stdout);
	RI i; for (scanf("%d%d",&n,&q);q;--q)
	{
		scanf("%s%d%d",opt+1,&l,&r);
		if (opt[2]=='A')
		{
			ifo it=SEG.query(l,r); int ret=0;
			for (i=0;i<4;++i) ret=max(ret,it.d[i]);
			printf("ANSWER %d\n",ret);
		} else
		{
			scanf("%d",&x); ifo it;
			for (i=0;i<4;++i)
			{
				while (x%pri[i]==0) x/=pri[i],++it.d[i];
			}
			SEG.modify(l,r,it);
		}
	}
	return 0;
}

H. Delivery Route

这题纯被祁神秒了，我就纯爬上去实现了一波，结果还因为拓扑排序刚开始没给所有零度点入队挂了两发

注意题目给出的单向边的性质，我们可以先用双向边把图缩成若干个连通块，那么这些单向边只能用于连接不同的连通块（否则就违背题中的限制）

那么很自然想到对于缩点后的图（一定是DAG）跑拓扑排序来维护最短路信息，而一个连通块内部由于边权均非负因此可以用Dijkstra来更新最短路信息

注意这里连通块内的最短路是伪多源最短路，只需要直接把所有可能作为起点的点扔进堆中即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<queue>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=50005,INF=1e18;
int n,m1,m2,s,x[N],y[N],z[N],fa[N],rst[N],idx,bel[N],deg[N],dis[N],vis[N];
vector <pi> G1[N],G2[N]; vector <int> pnt[N];
inline int getfa(CI x)
{
	return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
inline void Dijkstra(CI id)
{
	priority_queue <pi,vector <pi>,greater <pi>> hp;
	for (auto x:pnt[id]) if (dis[x]!=INF) hp.push(pi(dis[x],x));
	while (!hp.empty())
	{
		int now=hp.top().second; hp.pop();
		if (vis[now]) continue; vis[now]=1;
		for (auto [to,w]:G1[now])
		if (dis[to]>dis[now]+w) hp.push(pi(dis[to]=dis[now]+w,to));
	}
}
signed main()
{
	//freopen("H.in","r",stdin); freopen("H.out","w",stdout);
	RI i; for (scanf("%lld%lld%lld%lld",&n,&m1,&m2,&s),i=1;i<=n;++i) fa[i]=i;
	for (i=1;i<=m1;++i)
	{
		int x,y,z; scanf("%lld%lld%lld",&x,&y,&z); fa[getfa(x)]=getfa(y);
		G1[x].push_back(pi(y,z)); G1[y].push_back(pi(x,z));
	}
	for (i=1;i<=n;++i)
	{
		int tmp=getfa(i); if (!rst[tmp]) rst[tmp]=++idx;
		bel[i]=rst[tmp]; pnt[bel[i]].push_back(i);
	}
	for (i=1;i<=m2;++i)
	{
		scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
		G2[bel[x[i]]].push_back(pi(bel[y[i]],i)); ++deg[bel[y[i]]];
	}
	for (i=1;i<=n;++i) dis[i]=INF; dis[s]=0;
	queue <int> q; for (i=1;i<=idx;++i) if (!deg[i]) q.push(i);
	while (!q.empty())
	{
		int now=q.front(); q.pop(); Dijkstra(now);
		for (auto [to,id]:G2[now])
		{
			if (!--deg[to]) q.push(to);
			if (dis[x[id]]!=INF) dis[y[id]]=min(dis[y[id]],dis[x[id]]+z[id]);
		}
	}
	for (i=1;i<=n;++i) if (dis[i]==INF) puts("NO PATH"); else printf("%lld\n",dis[i]);
	return 0;
}

I. Base62

什么C语言课后习题，但是数据范围比较大需要写高精度，不过无所谓徐神用Py秒了

MAP = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

if __name__ == "__main__":
    x, y, z = input().split()
    x = int(x)
    y = int(y)
    Z = 0
    for c in z:
        Z = Z * x + MAP.find(c)
    ans = ""
    if Z == 0:
        ans = "0"
    while Z > 0:
        ans += MAP[Z % y]
        Z = Z // y
    Ans = ""
    for c in reversed(ans):
        Ans += c
    print(Ans)

J. Toad's Travel

很有意思的一个题，被我们最后胡乱一通操作直接艹过去了

首先考虑如果我们要求的是从\(1\)出发，经过所有边后最后返回\(1\)点的代价，那么显然就是环边各走一次，非环边各走两次

考虑现在我们不需要回到出发点，其实就相当于找一条用非环边构成的路径，钦定上面的边都只走一次

但后面祁神发现我们有可能可以通过再走一些环边来连通一些本来不相连的非环边路径，可能可以得到更好的解

因此后面发现，我们可以把所有环边的权值取反，此时就是要找一个从\(1\)出发，不经过重复边的路径，使得这条路径的权值和最大

然后当我写完大力SPFA后就发现一个严重的问题，因为图中的边都是双向边，那么如果有一条边权为正的双向边拿这个图中就有正环，直接跑不出来了

但后面祁神发现其实我们可以直接给正权边（即非环边）定向，我们钦定这条边的方向总是从更靠近\(1\)号点的那个点指向另一个点的，对于负权边的话就不用处理

最后写完过了样例就直接一发过了，虽然喜提最劣解，但毕竟和好多人写的圆方树上DP比起来这个实在是好写好想太多了

#include<cstdio>
#include<iostream>
#include<queue>
#include<utility>
#include<vector>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=200005,INF=1e18;
int n,m,x[N],y[N],z[N],fa[N],anc[N],pre[N],dep[N],cyc[N],vis[N],dis[N],ans; vector <pi> G1[N],G2[N];
inline int getfa(CI x)
{
	return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
inline void DFS(CI now=1,CI fa=0)
{
	anc[now]=fa; for (auto [to,id]:G1[now])
	if (to!=fa) dep[to]=dep[now]+1,pre[to]=id,DFS(to,now);
}
inline void addedge(int x,int y,CI z)
{
	G2[x].push_back(pi(y,z));
}
signed main()
{
	//freopen("J.in","r",stdin); freopen("J.out","w",stdout);
	RI i; for (scanf("%lld%lld",&n,&m),i=1;i<=n;++i) fa[i]=i;
	vector <int> E; for (i=1;i<=m;++i)
	{
		scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
		if (getfa(x[i])==getfa(y[i])) { E.push_back(i); continue; }
		fa[getfa(x[i])]=getfa(y[i]);
		G1[x[i]].push_back(pi(y[i],i)); G1[y[i]].push_back(pi(x[i],i));
	}
	DFS(); for (auto id:E)
	{
		int u=x[id],v=y[id]; cyc[id]=1;
		if (dep[u]<dep[v]) swap(u,v);
		while (dep[u]>dep[v]) cyc[pre[u]]=1,u=anc[u];
		while (u!=v) cyc[pre[u]]=cyc[pre[v]]=1,u=anc[u],v=anc[v];
	}
	for (i=1;i<=m;++i) if (cyc[i])
	{
		ans+=z[i]; addedge(x[i],y[i],-z[i]); addedge(y[i],x[i],-z[i]);
	} else
	{
		ans+=2LL*z[i]; if (dep[x[i]]>dep[y[i]]) swap(x[i],y[i]); addedge(x[i],y[i],z[i]);
	}
	for (i=1;i<=n;++i) dis[i]=-INF; dis[1]=0;
	queue <int> q; q.push(1); vis[1]=1;
	while (!q.empty())
	{
		int now=q.front(); q.pop(); vis[now]=0;
		for (auto [to,w]:G2[now])
		if (dis[to]<dis[now]+w)
		{
			dis[to]=dis[now]+w;
			if (!vis[to]) q.push(to),vis[to]=1;
		}
	}
	int tmp=0; for (i=1;i<=n;++i) tmp=max(tmp,dis[i]);
	return printf("%lld",ans-tmp),0;
}

K. Largest Common Submatrix

徐神妙了此题，但我是一点不会

大致思路应该就是把\(A\)种的每个数在\(B\)中对应的位置找到，然后搞一个类似于悬线法的东西，单调栈维护即可

#include <bits/stdc++.h>

using pii = std::pair<int, int>;

constexpr int $n = 1000;

int n, m, A[$n][$n], B[$n][$n], le[$n][$n], up[$n][$n];
pii AB[$n][$n];

pii Bc[$n * $n + 100];

int main() {
	// freopen("K.in", "r", stdin);
	std::ios::sync_with_stdio(false);
	memset(Bc, -1, sizeof(Bc));
	std::cin >> n >> m;
	for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) std::cin >> A[i][j];
	for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) {
		std::cin >> B[i][j];
		Bc[ B[i][j] ] = {i, j};
	}
	for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j)
		AB[i][j] = Bc[ A[i][j] ];
	for(int i = 0; i < n; ++i) le[i][0] = (AB[i][0].first >= 0);
	for(int i = 0; i < n; ++i) for(int j = 1; j < m; ++j) {
		if(AB[i][j].first < 0) le[i][j] = 0;
		else if (
			AB[i][j - 1].first  == AB[i][j].first &&
			AB[i][j - 1].second == AB[i][j].second - 1
		) le[i][j] = le[i][j - 1] + 1;
		else le[i][j] = 1;
	}
	for(int j = 0; j < m; ++j) up[0][j] = (AB[0][j].first >= 0);
	for(int i = 1; i < n; ++i) for(int j = 0; j < m; ++j) {
		if(AB[i][j].first < 0) up[i][j] = 0;
		else if (
			AB[i - 1][j].first  == AB[i][j].first  - 1 &&
			AB[i - 1][j].second == AB[i][j].second
		) up[i][j] = up[i - 1][j] + 1;
		else up[i][j] = 1;
	}
//	for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j)
//		std::cerr << up[i][j] << char(j == m - 1 ? 10 : 32);
	int ans = 0;
	static int stax[$n + 5] = {0}, stay[$n + 5] = {-1};
	for(int i = 0; i < n; ++i) {
		int top = 0;
		auto popStack = [&ans, &top, i] (int x, int y) {
			int res = x;
			while(y <= stay[top]) {
				res = stax[top];
				ans = std::max(ans, (x - stax[top]) * stay[top]);
				// std::cerr << "Upd " << i << ": " << stax[top] << ' ' << x - 1 << ' ' << stay[top] << char(10);
				top -= 1;
			}
			return res;
		};
		for(int j = 0; j < m; ++j) {
			int x;
			if(le[i][j] <= 1) popStack(j, 0), x = j;
			else              x = popStack(j, up[i][j]);
			if(up[i][j])
				stax[++top] = x,
				stay[  top] = up[i][j];
		}
		popStack(m, 0);
	}
	std::cout << ans << char(10);
	return 0;
}

L. Xian Xiang

题解说是状压DP，但不告诉我状态方程我怎么知道怎么写啊喂

M. Crazy Cake

群计数题，妈的没有数理基础做不来一点

N. Fibonacci Sequence

纯签到题

#include<cstdio>
using namespace std;
int main()
{
    return puts("1 1 2 3 5"),0;
}

Postscript

今天这场训完后明天晚上再找一场打打就差不多了，合肥之前也没机会再训了