挑战赛 #7 题解

userId_undefined

暑 假 神（开学祭

秩序白银

2024-08-07 17:16:37

发布于：上海

78阅读
0回复
0点赞

本次挑战赛的难度有挑战赛的难度。听君一席话，如听一席话

T1

直接拓扑排序一下即可。注意可能有非 11 源点，需要把这些点的路径数量设为 00 再加入搜索队列，时间复杂度 O(n+m)O(n+m)。

#include <cstdio>
#include <memory.h>
#include <queue>
using namespace std;


vector<int>g[5005];
int ind[5005],cnt[5005];

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int k;scanf("%d",&k);
		for(int j=1;j<=k;j++){
			int b;
			scanf("%d",&b);
			g[i].push_back(b);
			ind[b]++;
		}
	}
	queue<int>q;
    q.push(1);cnt[1]=1;
	for(int i=2;i<=n;i++){
		if(ind[i]==0){
			q.push(i);
			cnt[i]=0;
		}
	}
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=0;i<g[x].size();i++){
			cnt[g[x][i]]+=cnt[x];
			cnt[g[x][i]]%=114514;
			ind[g[x][i]]--;
			if(ind[g[x][i]]==0) q.push(g[x][i]);
		}
	}
	printf("%d",cnt[n]%114514);
		
	return 0;
}

T2

无论如何旋转都一样，相当于对于每一个 1≤i,j≤n1\leq i,j\leq n，都有 a[i][j]=a[j][n−i+1]=a[n−j+1][i]=a[n−i+1][n−j+1]a[i][j]=a[j][n-i+1]=a[n-j+1][i]=a[n-i+1][n-j+1]。因此，我们考虑将这些字符中的最大值分别减去每一个字符，得到的结果即为让这四个字符相同需要的操作次数。时间复杂度 O(n2)O(n^2)。

#include <cstdio>
#include <algorithm>
using namespace std;
char a[1005][1005];

int main(){
	int T;scanf("%d",&T);while(T--){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
	long long ans=0;
	for(int i=1;i<=n>>1;i++)
		for(int j=1;j<=n>>1;j++)
			ans+=(max(max(a[i][j],a[j][n-i+1]),max(a[n-j+1][i],a[n-i+1][n-j+1]))<<2)-a[i][j]-a[j][n-i+1]-a[n-j+1][i]-a[n-i+1][n-j+1];

	printf("%lld\n",ans);
	}
	return 0;
}

T3

考虑对 aj−ai=j−ia_j-a_i=j-i 条件进行变换：aj−j=ai−ia_j-j=a_i-i。因此我们可以求出对于每一个 i≤ni\leq n 的 ai−ia_i-i，并对其进行桶计数。容易得出，若一个桶内有 xx 个元素，则这个桶对答案的贡献为 x(x−1)2\dfrac{x(x-1)}2。时间复杂度 O(n)O(n)。

实现时有一些小细节：答案要开 long long，并且桶可能被放入负数，可以考虑对每一个放入桶中的元素都 +2×105+2\times 10^5。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <string> 
#include <unordered_map>
#include <cmath> 
#include <memory.h>
#define map unordered_map
#define ll long long
#define ull unsigned long long
using namespace std;

namespace io{
const int size=(1<<20)+1;
char buf[size],*p1=buf,*p2=buf;
char buffer[size];
int op1=-1;
const int op2=size-1;
inline char readchar() {
	if(p1!=p2) {
		return *p1++;
	}
	return p1==(p2=(p1=buf)+fread(buf,1,size-1,stdin))?EOF:*p1++;
}
inline void flush() {
	fwrite(buffer,1,op1+1,stdout),op1=-1;
}
inline void writechar(const char &x) {
	if(op1==op2) flush();
	buffer[++op1]=x;
}
#define gc readchar
#define pc writechar
#define el pc(10)
#define sp pc(32)
inline int readi(){
	int x=0;bool w=0;
	char ch=gc();
	while(ch<'0'||ch>'9'){
		if(ch=='-') w=1;
		ch=gc();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=gc();
	}
	return w?-x:x;
}

inline ll readl(){
	ll x=0;bool w=0;
	char ch=gc();
	while(ch<'0'||ch>'9'){
		if(ch=='-') w=1;
		ch=gc();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=gc();
	}
	return w?-x:x;
}

void writei(int x){
	if(x<0) pc('-'),x=-x;
	if(x>9) writei(x/10);
	pc((x%10)^48);
}

void writel(ll x){
	if(x>9) writel(x/10);
	pc((x%10)^48);
}
};// io
using namespace io; 


#define prc(x) printf(#x":%c\n",x)
#define pri(x) printf(#x":%d\n",x)
#define prl(x) printf(#x":%lld\n",x)

int b[400005];
int main(){
	int n=readi();
	for(register int i=1;i<=n;i++)
		b[readi()-i+200000]++;
	
	long long ans=0;
	for(register int i=1;i<=n+200000;i++)
		ans+=(b[i]*(b[i]-1))>>1;
	writel(ans);flush();
	
	return 0;
}

T4

直接广搜即可，步长分别为 (−2,−2),(2,−2),(−2,2),(2,2)(-2,-2),(2,-2),(-2,2),(2,2)。时间复杂度 O(n2)O(n^2)。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <string> 
#include <map>
#include <unordered_map>
#include <cmath> 
#include <memory.h>
#include <cstring>
#define map unordered_map
using namespace std;

#define prc(x) printf(#x":%c\n",x)
#define pri(x) printf(#x":%d\n",x)
#define prl(x) printf(#x":%lld\n",x)
#define ll long long
#define ull unsigned long long

#define check(x,y) (x>=0&&x<=500&&y>=0&&y<=500)
struct node{int x,y;};

int dx[]={-2,-2,2,2},
    dy[]={-2,2,-2,2};
int vis[505][505];
int main(){
	int n,a,b,c,d;scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
	vis[a][b]=1;
	queue<node>q;q.push({a,b});
	while(!q.empty()){
		int x=q.front().x,y=q.front().y;q.pop();
		if(x==c&&y==d){
			puts("YES");
			return 0;
		}
		for(int i=0;i<=3;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(check(nx,ny)&&!vis[nx][ny]){
				vis[nx][ny]=1;
				q.push({nx,ny});
			}
		}
	}
	puts("NO");
	return 0;
}

T5

发现 nn 的数据范围极小，考虑暴力搜索。直接深搜即可。发现答案差值不会太大（不会超过 10910^9），为了避免爆 long long，可以在 lil_i 过大（大约 101010^{10}）时直接剪枝即可。但是过程中仍然可能爆 long long（6464 位乘 3232 位时），由于我不想写高精度，就用了 long long long long __int128。时间复杂度（大约） O(2n)O(2^n)。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <string> 
#include <map>
#include <unordered_map>
#include <cmath> 
#include <memory.h>
#include <cstring>
#define map unordered_map
using namespace std;

#define prc(x) printf(#x":%c\n",x)
#define pri(x) printf(#x":%d\n",x)
#define prl(x) printf(#x":%lld\n",x)
#define ll long long
#define ull unsigned long long

#define llll __int128
ll ans=1ll<<48;
llll inf=1ll<<48;
int l1[15],r1[15],n;
void dfs(int x,llll l,llll r){
//	pri((int)x);
	if(l>inf) return;
	if(x==n+1){
		ans=min(ans,abs((ll)(l-r)));
		return;
	}
	for(int i=x+1;i<=n;i++){
		dfs(i,l*l1[i],r+r1[i]);
	}
	if(x!=0)dfs(n+1,l,r);
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",l1+i,r1+i);
	dfs(0,1,0);
	printf("%lld",ans);
	
	return 0;
}

T6

好吧，这次的签到题竟然事 T6，让我想起了某届欢乐赛。

思路：找到 ? 所处的那一行，然后看那一行少了哪个字母。

int main(){
	char s[4][4];
	scanf("%s%s%s",s[1]+1,s[2]+1,s[3]+1);
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			if(s[i][j]=='?'){
				char c1=s[i][1],c2=s[i][2],c3=s[i][3];
               // printf("%c%c%c",c1,c2,c3);
				if(c1=='?') c1=c3;
				if(c2=='?') c2=c3;
				if(c1>c2) swap(c1,c2);
				if(c1!='A') putchar('A');
				else if(c2!='C') putchar('C');
				else putchar('B');
			}
		}
	}
	return 0;
}

后记

好吧，你说得对，但是这篇题解确实都是在集训营里肝出来的，所以非常生草。

userId_undefined
去预览
0/2000

全部评论 3

热门讨论