Comet OJ - Contest #13[A-D]

题目链接:https://www.cometoj.com/contest/71/problems

A.「壶中的大银河」

水题

B.「龙颈之玉 -五色的弹丸-」

用一个双向队里维护一下贪吃蛇某个点的前一个位置方向是啥就好了

#include<bits/stdc++.h>
#define x first
#define y second
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair <int,int> pa;
const int mx = 400 + 10;
const int mod = 1e9 + 7;
const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};
char s[mx][mx];
char t[mx*mx];
int n,m;
deque <int> deq;
int dir(char ch)
{
	if (ch=='W') return 1;
	if (ch=='S') return 0;
	if (ch=='A') return 3;
	return 2;
}
bool out(pa now)
{
	return now.x < 0 || now.y < 0 || now.x == n || now.y == m;
}
int main()
{   
	scanf("%d%d",&n,&m);
	pa now;
	for (int i=0;i<n;i++) {
		scanf("%s",s[i]);
		for (int j=0;j<m;j++) {
			if (s[i][j]=='@')
				now = pa(i,j);
		}
	}
	s[now.x][now.y] = '.';
	scanf("%s",t);
	for (int i=0;t[i];i++) {
		int d = dir(t[i]);
		pa nxt = pa(now.x+dx[d],now.y+dy[d]);
		if (out(nxt)) return 0*puts("GG");
		if (s[nxt.x][nxt.y]=='o') {
			s[nxt.x][nxt.y] = '.';
			deq.push_front(d);
		} else {
			deq.push_front(d);
			deq.pop_back();
		}
		now = nxt;
	}
	s[now.x][now.y] = '@';
	//cout << now.x << " " << now.y << endl;
	while (!deq.empty()) {
		int d = deq.front();
		deq.pop_front();
		pa nxt = pa(now.x+dx[d^1],now.y+dy[d^1]);
		if (s[nxt.x][nxt.y] == '.')
			s[nxt.x][nxt.y] = 'X';
		now = nxt;
	}
	for (int i=0;i<n;i++)
		puts(s[i]);
    return 0;
}

C.「佛御石之钵 -不碎的意志-」

1.只保留值是0的点，更新的时候也只更新这些点

2.维护一每行值是0的点

3.用并查集记录一下转态

步骤2用set会T，所以又得用并查集来维护0值的点

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair <int,int> pa;
const int mx = 1e3 + 10;
const int mod = 1e9 + 7;
const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};
char s[mx][mx];
int st[mx][mx];
int fa[mx*mx],ans;
int w[mx][mx];
int find(int x,int *f)
{
	return x==f[x]?x:f[x]=find(f[x],f);
}
inline void merge(int u,int v,int *f)
{
	//cout << 1 << endl;
	int fu = find(u,f);
	int fv = find(v,f);
	if (fu != fv) {
		if (f == fa)
			ans--;
		f[fv] = fu;
	}
}
int main()
{  
	int n,m,q;
	scanf("%d%d",&n,&m);
	ans = 0;
	for (int i=1;i<=n;i++) {
		scanf("%s",s[i]+1);
		for (int j=1;j<=m;j++) {
			w[i][j] = (i-1)*mx + j;
			fa[w[i][j]] = w[i][j];
			if (s[i][j]=='1') {
				ans++;
				if (s[i-1][j]=='1') 
					merge(w[i-1][j],w[i][j],fa);
				if (s[i][j-1]=='1') 
					merge(w[i][j-1],w[i][j],fa);
			}
		}
	} 
	for (int i=1;i<=n;i++) {
		st[i][m+1] = m+1;
		for (int j=m;j>=1;j--){
			st[i][j] = j;
			if (s[i][j]=='1') merge(j+1,j,st[i]);
		}
	}
	//cout << ans << endl;
	scanf("%d",&q);
	while (q--) {
		int x1,x2,y1,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		for (int i=x1;i<=x2;i++) {
			int tmp = y1;
			while(1) {
				tmp = find(tmp,st[i]);
				if (tmp > y2) break;
				int id = w[i][tmp];
				ans++;
				if (s[i-1][tmp]=='1') 
					merge(w[i-1][tmp],id,fa);
				if (s[i][tmp-1]=='1') 
					merge(w[i][tmp-1],id,fa);
				if (s[i+1][tmp]=='1')
					merge(w[i+1][tmp],id,fa);
				if (s[i][tmp+1]=='1')
					merge(w[i][tmp+1],id,fa);	
					
				s[i][tmp] = '1';
				merge(tmp+1,tmp,st[i]);
				tmp++;
			}
		}
		printf("%d\n",ans);
	}
    return 0;
}

D.「火鼠的皮衣 -不焦躁的内心-」

将

变为

,那么原式就会变为一个二项式，即为

,最后结果即为

,由原式可得我们需要的是没有根号a部分的项的和，即为x，所以用一个快速幂求一下上面这个式子，然后输出x即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5+5;
typedef long long ll;
ll n,a,b,p;
struct node
{
	__int128 x,y;
	node operator * (node A) {
		node now = {(x*A.x+y*A.y%p*a)%p,(x*A.y+y*A.x)%p};
		return now;
	}
};
node qpow(ll c) {
	node ans = {1,0};
	node base = {b,1};
	while (c) {
		if (c&1) ans = ans*base;
		c >>= 1;
		base = base*base;
	}
	return ans;
}
void print(__int128 v) {
	if (v>9) print(v/10);
	putchar(v%10+'0'); 
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%lld%lld%lld%lld",&n,&a,&b,&p);
		node ans = qpow(n);
		print(ans.x);puts("");
	}
	return 0;
}