首页 > 代码库 > 2017-5-20-Train: 喵哈哈村的魔法考试 Round #17 (Div.2)
2017-5-20-Train: 喵哈哈村的魔法考试 Round #17 (Div.2)
描述
喵哈哈村的一堆人在前往北京的路上，发现了一个洞穴。由于好奇心大作，于是准备前往洞穴进行探险。
但是有一些人并不愿意前往洞穴，于是他们决定玩以下游戏，来看是否能够去秘境探险：
这儿有n个数，如果所有数的乘积是k的倍数，那么就去探险，否则就不去。
现在问你是否会去。
输入
本题包含若干组测试数据。第一行两个整数n,k，表示数的个数，和k。第二行n个整数，a[i]。满足1<=n<=1000,1<=k,a[i]<=1e6
输出
如果要去的话，输出Yes，否则输出N
样例输入1
复制
3 51 2 43 81 2 4
样例输出1
NoYes
Solve:
直接按照模的性质来就好了
Code:
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 LL n , k , x; 5 LL ans; 6 int main() 7 { 8 while(~scanf("%lld%lld" , &n , &k)) 9 {10 ans = 1;11 for(int i = 1 ; i <= n ; ++i)12 {13 scanf("%lld" , &x);14 ans = ans * x % k;15 }16 if(!ans)17 puts("Yes");18 else19 puts("No");20 }21 22 return 0;23 }
描述
喵哈哈村的一堆人在前往北京的路上，发现了一个洞穴。由于好奇心大作，于是准备前往洞穴进行探险。
秘境探险的第一关，是答对秘境门口的招牌上的问题。
招牌上的问题这样写道：
我想每次查询区间的异或值，请你帮帮我。
输入
本题包含若干组测试数据。第一行一个n，表示有n个数。第二行n个整数，表示每个数a[i]第三行一个q，表示查询的个数。接下来q行，每行l,r，表示要查询的区间。满足1<=n,q<=1e5 0<=a[i]<=1e6 1<=l<=r<=n
输出
对于每组询问，输出答案。
样例输入1
复制
31 2 331 12 2 1 3
样例输出1
120
Solve:
处理前缀异或,查询像前缀和那样查询就行了
Code:
1 #include <bits/stdc++.h> 2 using namespace std; 3 static const int MAXN = 1e5 + 10; 4 typedef long long LL; 5 LL pre[MAXN]; 6 int n , q; 7 8 int main() 9 {10 while(~scanf("%d" , &n))11 {12 for(int i = 1 ; i <= n ; ++i)13 {14 scanf("%lld" , &pre[i]);15 pre[i] ^= pre[i - 1];16 }17 18 scanf("%d" , &q);19 while(q--)20 {21 int x , y;22 scanf("%d%d" , &x , &y);23 printf("%lld\n" , pre[y] ^ pre[x - 1]);24 }25 }26 }
描述
喵哈哈村的一堆人在前往北京的路上，发现了一个洞穴。由于好奇心大作，于是准备前往洞穴进行探险。
洞穴里面没想到别有一番风景，但是这个风景好像有一些神秘。
我们可以把风景看作一个n*n的地图，每个点有它的初始高度。有一个小球，它只能从高处往低处滑【严格大于】。但是由于地势经常变动，高度经常变化；同时，喵哈哈村发现，有些位置会不能滑动。
现在，给出每个n*n个点的初始高度，并给出m个命令:
C a b c表示坐标为a,b的点的高度改为c；
S a b c d表示左上角为a,b右下角为c,d的矩形地区不能继续经过；
B a b c d表示左上角为a b,右下角为c d的矩形地区可以经过；
Q表示询问现在该风景小球可以走的最长路径为多少。对于每个Q要作一次回答。
输入
第一行n，第二行开始n*n的地图，意义如上；接下来一个m，然后是m个命令，如上1<=n<=700;1<=m<=1000000;其中Q、S、B操作分别<=100;题中所有数据不超过2*10^9的正整数
输出
对于每个Q，输出答案。
样例输入1
复制
51 2 3 4 510 9 8 7 611 12 13 14 1520 19 18 17 1621 22 23 24 255C 1 1 3QS 1 3 5 5S 3 1 5 5Q
样例输出1
243
Solve:
经典滑雪问题,直接暴力修改,数据不大
Code:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define CLR(x , v) memset(x , v , sizeof(x)) 5 6 static const int MAXN = 800; 7 static const int dirx[4] = {1 , 0 , -1 , 0}; 8 static const int diry[4] = {0 , 1 , 0 , -1}; 9 10 bool vis[MAXN][MAXN]; 11 int data[MAXN][MAXN]; 12 int dp[MAXN][MAXN]; 13 int n , m; 14 15 int Dfs(int x , int y) 16 { 17 if(vis[x][y]) 18 return 0; 19 20 if(dp[x][y]) 21 return dp[x][y]; 22 23 dp[x][y] = 1; 24 25 for(int i = 0 ; i < 4 ; ++i) 26 { 27 int nx = x + dirx[i] , ny = y + diry[i]; 28 29 if(nx > n || ny > n || nx < 1 || ny < 1) 30 continue; 31 32 if(data[nx][ny] >= data[x][y]) 33 continue; 34 35 dp[x][y] = max(dp[x][y] , Dfs(nx , ny) + 1); 36 } 37 38 return dp[x][y]; 39 } 40 41 int main() 42 { 43 scanf("%d" , &n); 44 for(int i = 1 ; i <= n ; ++i) 45 { 46 for(int j = 1 ; j <= n ; ++j) 47 { 48 scanf("%d" , &data[i][j]); 49 } 50 } 51 52 scanf("%d" , &m); 53 while(m--) 54 { 55 char cmd[3] = {‘\0‘}; 56 int a , b , c , d; 57 scanf(" %s" , cmd); 58 if(cmd[0] == ‘Q‘) 59 { 60 int ans = 0; 61 memset(dp , 0 , sizeof(dp)); 62 for(int i = 1 ; i <= n ; ++i) 63 { 64 for(int j = 1 ; j <= n ; ++j) 65 { 66 ans = max(ans , Dfs(i , j)); 67 } 68 } 69 70 printf("%d\n" , ans); 71 } 72 else if(cmd[0] == ‘S‘) 73 { 74 scanf("%d%d%d%d" , &a , &b , &c , &d); 75 for(int i = a ; i <= c ; ++i) 76 { 77 for(int j = b ; j <= d ; ++j) 78 { 79 vis[i][j] = 1; 80 } 81 } 82 } 83 else if(cmd[0] == ‘B‘) 84 { 85 scanf("%d%d%d%d" , &a , &b , &c , &d); 86 for(int i = a ; i <= c ; ++i) 87 { 88 for(int j = b ; j <= d ; ++j) 89 { 90 vis[i][j] = 0; 91 } 92 } 93 } 94 else 95 { 96 scanf("%d%d%d" , &a , &b , &c); 97 data[a][b] = c; 98 } 99 }100 }
2017-5-20-Train: 喵哈哈村的魔法考试 Round #17 (Div.2)