Pontuação final: 100 + 95 + 0 + 20.

A. Operação Numérica (num)

Durante a competição, examinei os exemplos e o intervalo de dados. Como todos os números eram primos, pensei imediatamente em MDC e resolvi rapidamente.

Na verdade, esse processo de subtração e contagem de valores não repetidos é semelhante ao algoirtmo de Euclides. Não há muito o que explicar, apenas salvei o código.

#include<bits/stdc++.h>
using namespace std;
int T,n;
int gcd(int x,int y){
	if(!y) return x;
	return gcd(y,x%y);
}
void solve(){
	scanf("%d",&n);
	int k=0,mx=0,ans=0;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		if(!k) k=x;
		else k=gcd(k,x);
		mx=max(mx,x);
	}
	for(int i=k;i<=mx;i+=k) ans++;
	printf("%d\n",ans);
}
int main(){
	freopen("num.in","r",stdin);
	freopen("num.out","w",stdout);
	scanf("%d",&T);
	while(T--) solve();
}

B. Caminho Mínimo (path)

Este é um problema clássico de contagem do segundo menor caminho, usando Dijkstra com duas dimensões. Já havia resolvido este problema em uma competição anterior (26 de setembro), então consegui resolvê-lo rapidamente. Durante a prova, ficou preocupando se o Dijkstra conseguiria executar a tempo, mas depois percebi que essa é a única abordagem comum para este tipo de problema.

Por que recebi apenas 95 pontos? Porque não verifiquei se o segundo menor caminho atende ao requisito estrito (ser exatamente 1 maior que o menor).

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+10;
const ll mod=998244353;
int n,m;
ll cnt[N][2];
int vis[N][2],d[N][2];
int idx,e[N],nxt[N],head[N];
void add(int x,int y){
	e[++idx]=y;
	nxt[idx]=head[x];
	head[x]=idx;
}
void dij(){
	priority_queue<pair<pair<int,int>,int> > q;
	memset(d,0x3f,sizeof d);
	q.push(make_pair(make_pair(0,1),0));
	d[1][0]=0;
	cnt[1][0]=1;
	while(q.size()){
		int x=q.top().first.second,t=q.top().second;
		q.pop();
		if(vis[x][t]) continue;
		vis[x][t]=1;
		for(int i=head[x];i;i=nxt[i]){
			if(d[e[i]][0]>d[x][t]+1){
				d[e[i]][1]=d[e[i]][0],cnt[e[i]][1]=cnt[e[i]][0];
				q.push(make_pair(make_pair(-d[e[i]][1],e[i]),1));
				d[e[i]][0]=d[x][t]+1,cnt[e[i]][0]=cnt[x][t];
				q.push(make_pair(make_pair(-d[e[i]][0],e[i]),0));
			}
			else if(d[e[i]][0]==d[x][t]+1) cnt[e[i]][0]=(cnt[e[i]][0]+cnt[x][t])%mod;
			else if(d[e[i]][1]>d[x][t]+1){
				d[e[i]][1]=d[x][t]+1,cnt[e[i]][1]=cnt[x][t];
				q.push(make_pair(make_pair(-d[e[i]][1],e[i]),1));
			}
			else if(d[e[i]][1]==d[x][t]+1) cnt[e[i]][1]=(cnt[e[i]][1]+cnt[x][t])%mod;
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y); 
		add(x,y);
		add(y,x);
	}
	dij();
	if(d[n][0]+1!=d[n][1]||!d[n][0]||d[n][0]==0x3f3f3f3f) puts("0");
	else printf("%lld\n",cnt[n][1]);
}

C. Faísca (fire)

A solução correta ainda não foi estudada. Provavelmente envolve processamento offline com árvore de segmentos e union-find. Acredito que preciso melhorar minha capacidade de implementar soluções por força bruta antes da próxima competição.

Durante a competição, parece que na última hora minha mente estava confusa. Escrevi uma solução baseada em propriedades de cadeia despreocupadamente e descobri que estava errada após a prova. Não sei implementar busca em profundidade para 20 pontos.

Por isso, esttudei rapidamente busca em árvore. Agora sei fazer. Este é o código para 20 pontos.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5+110;
int n,q,k;
ll ans;
int vis[N];
int idx,e[N],w[N],nxt[N],head[N];
void add(int x,int y,int z){
	e[++idx]=y;
	w[idx]=z;
	nxt[idx]=head[x];
	head[x]=idx;
}
void dfs(int x){
	vis[x]=1;
	for(int i=head[x];i;i=nxt[i]){
		if(w[i]>k) continue;
		if(!vis[e[i]]){
			ans+=w[i];
			dfs(e[i]);
		}
	}
} 
int main(){
	scanf("%d",&n);
	for(int i=2;i<=n;i++){
		int x,z;
		scanf("%d%d",&x,&z);
		add(x,i,z);
	}
	scanf("%d",&q);
	while(q--){
		int u;
		scanf("%d%d",&u,&k);
		dfs(u);
		printf("%lld\n",ans);
		memset(vis,0,sizeof vis);
		ans=0;
	}
}

D. Exclusão (exc)

Similar ao anterior, acho que não preciso mais estudar isso. Esta é a solução por força bruta para 30 pontos. Por que na prova a solução por força bruta recebeu apenas 20 pontos? Porque esquecemos de usar long long na exponenciação rápida, causando overflow.

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N=2e5+10;
const ll mod=998244353;
int n,a,b;
ll ans;
int t[N];
map<ull,int> vis;
bool check(int m){
	if(m==1) return 1;
	for(int i=1;i<=m;i++)
		for(int j=i+1;j<=m;j++)
			if(t[i]*a==t[j]||t[j]*a==t[i]||t[i]*b==t[j]||t[j]*b==t[i]) return 0;
	return 1;
}
void js(int m){
	ull tot=0;
	for(int i=1;i<=m;i++) tot=tot*131+t[i]*131;
	if(!vis[tot]){vis[tot]=1;ans++;}
}
void dfs(int x,int tot){
	if(check(tot)) js(tot);
	if(x==n+1) return;
	t[tot+1]=x;
	dfs(x+1,tot+1);
	t[tot+1]=0;
	dfs(x+1,tot);
}
ll ksm(ll a,ll b){
	ll tot=1;
	while(b){
		if(b&1) tot=(tot*a)%mod;
		b>>=1;
		a=(a*a)%mod;
	}
	return tot%mod;
}
int main(){
	scanf("%d%d%d",&n,&a,&b);
	if(a==1&&b==1){
		printf("%lld",ksm(2,n));
		return 0;
	}
	if(n<=15){
		dfs(1,0);
		printf("%lld",ans);
		return 0;
	}
}