浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛（同步赛）

D-涛涛和策策的游戏：博弈论(sg)

思路：游戏输的一方是找不到一个大于1的数，那么就是说每个人都想最先让所有数变为1。所有如果双方都会考虑让对方把这个数变成素数，所以我们就去找每个数有多少个素因子，这就类似于尼姆游戏了，每个数相当于每堆石子，素因子个数相当于每堆石子的个数，然后异或一下便可得到答案。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <time.h>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;

using namespace std;

ll zhi(int x)
{
    ll cnt = 0;
	for(int i = 2; i <= sqrt(x); i++){
		if(x % i == 0){
			while(x % i == 0){
				cnt++;
				x /= i;
			}
		}
	}
	if(x > 1) cnt++;
	return cnt;	
} 

int main()
{ 
    int n,x;
    scanf("%d",&n);
    ll ans = 0;
    for(int i = 1; i <= n; i++){
    	scanf("%d",&x);
    	ans ^= zhi(x);
	}
	if(ans == 0) printf("TT txdy!");
	else printf("CC yyds!");
	return 0;
}

F-学长的白日梦：快速幂

python处理大数

mod = 9999999967
def f(a,b):
    res = 1
    while(b != 0):
        if(b & 1):
            res = (res*a) % mod
        b = b >> 1
        a = (a*a)%mod
    return res%mod
t = int(input())
while t != 0:
    a,b = map(int,input().split())
    print(f(a,b)%mod)
    t = t - 1

k-dousha篮球时间

注意题目给的01串就是初始串。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <time.h>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;

using namespace std;

int main()
{
	int n,q;
	char s[1000005];
	scanf("%d%d",&n,&q);
	scanf("%s",s+1);
	int ans = 0;
	s[0] = '0';
	s[n+1] = '0';
	for(int i = 1; i <= n; i++){
		if(s[i] == '1' && s[i - 1] == '0')
		    ans++;
	}
	printf("%d\n",ans);
	int x;
	for(int i = 1; i <= q; i++){
		scanf("%d",&x);
		if(s[x] == '0'){
			s[x] = '1';
			if(s[x-1] == '0' && s[x+1] == '0'){
			    ans++;
		    }
		    else if(s[x-1] == '1' && s[x+1] == '1'){
		    	ans--;
			}
			printf("%d\n",ans);
		}
		else{
			s[x] = '0';
			if(s[x-1] == '1' && s[x+1] == '1') ans++;
			else if(s[x-1] == '0' && s[x+1] == '0') ans--;
			printf("%d\n",ans);
		}
	} 
    return 0;    
}

M-灾难预警：bfs+二分

思路：先二分出不能通过的最高水位，然后判断当前水位是否超过这个临界点。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <time.h>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;

using namespace std;

struct node{
	int x,y;
	node(int a,int b){
		x = a;
		y = b;
	}
};

int a[1005][1005];
int dp[100005];
int vis[1005][1005];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int n,q,h;

bool check(int x,int y)
{
	if(x <= 0 || x > n || y <= 0 || y > n) return false;
	return true;
}

bool bfs(int k)
{
	memset(vis,0,sizeof(vis));
	queue<node>d;
	if(a[1][1] < k) {
		return false;
	}
	d.push(node(1,1));
	while(!d.empty()){
		node s = d.front();
		d.pop();
		if(s.x == n && s.y == n){
			return true;
		}
		int x,y;
		for(int i = 0; i < 4; i++){
			x = s.x + dir[i][0];
			y = s.y + dir[i][1];
			if(check(x,y) && !vis[x][y] && a[x][y] >= k){
				d.push(node(x,y));
				vis[x][y] = 1;
			}
		}
	} 
	return false; 
}

int main()
{
	scanf("%d",&n);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++) 
		    scanf("%d",&a[i][j]);
	int l = 0,r = 100001,ans = 0;
	while(l <= r){
		int mid = (l + r) >> 1;
	//	cout << mid<< endl;
		if(bfs(mid)){
			l = mid+1;
			ans = mid;
		}
		else r = mid - 1;
	}   
    scanf("%d",&q);
   // cout << ans << endl;
    while(q--){
    	scanf("%d",&h);
    	if(h > ans) printf("Hmmm\n");
    	else printf("Wuhu\n");
	}
    return 0;    
}