浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛（同步赛）
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;
}
投递华为技术有限公司等公司10个岗位
字节跳动公司福利 1229人发布