小J的五子棋
题目描述
小J非常热爱玩游戏，尤其喜欢五子棋。
五子棋是一款这样的游戏：
在一个N*N的网格上，玩家依次在格子上放下棋子，如果棋子在同一横排、同一竖排、同一斜线（有两条不同的斜线，从左上到右下以及从右上到左下）连续出现了五个，那么就满足了胜利条件。需要注意的是，与一般的五子棋不同，我们只考虑一个玩家的棋子，即不存在不同的颜色。
小J于是开始了一盘紧张刺激的五子棋。
小J的玩法和一般的玩法不同，小J喜欢先写下一个长度为M的放置棋子序列，然后依次放置棋子，直到满足胜利条件为止，或者说序列上的棋子都放置完了。
那么，小J想知道会在放置第几个棋子之后达到胜利条件。
对于30%的数据，1<=N,M<=10.
对于60%的数据，1<=N,M<=100.
对于100%的数据，1<=N<=20000,M<=200000.
输入格式
第一行两个正整数N,M，意义见题面。
接下来M行，每行两个整数x,y.（x,y）表示放置的棋子的坐标。保证1<=x,y<=N.
输出格式
一行一个整数，表示达到胜利条件时放置的棋子。如果达不到胜利条件，输出-1.
输入样例
5 5
1 1
2 2
3 3
4 4
5 5
输出样例
5
题解(暴力)
人人都会的大水题，空间512M，时间1S，不卡bool卡map。
bool是一个字节，map以后还是用hash代替吧。懒得动手没了20分QAQ。。。
代码
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#define N 20005
using namespace std;
int n, m;
bool M[N*N];
bool Judge(int x, int y){
int res = 0;
for(int i = y; i > 0; i--){
if(M[(x-1)*n+i]) res ++;
else break;
}
for(int i = y+1; i <= n; i++){
if(M[(x-1)*n+i]) res ++;
else break;
}
if(res >= 5) return true;
res = 0;
for(int i = x; i > 0; i--){
if(M[(i-1)*n+y]) res ++;
else break;
}
for(int i = x+1; i <= n; i++){
if(M[(i-1)*n+y]) res ++;
else break;
}
if(res >= 5) return true;
res = 0;
for(int i = x, j = y; i > 0 && j > 0; i--, j--){
if(M[(i-1)*n+j]) res ++;
else break;
}
for(int i = x+1, j = y+1; i <= n && j <= n; i++, j++){
if(M[(i-1)*n+j]) res ++;
else break;
}
if(res >= 5) return true;
res = 0;
for(int i = x, j = y; i > 0 && j <= n; i--, j++){
if(M[(i-1)*n+j]) res ++;
else break;
}
for(int i = x+1, j = y-1; i <= n && j > 0; i++, j--){
if(M[(i-1)*n+j]) res ++;
else break;
}
if(res >= 5) return true;
return false;
}
int main(){
scanf("%d%d", &n, &m);
int x, y;
for(int i = 1; i <= m; i++){
scanf("%d%d", &x, &y);
M[(x-1)*n+y] = true;
if(Judge(x, y)){
printf("%d\n", i);
return 0;
}
}
printf("-1\n");
return 0;
}小J爱gcd
题目描述
最大公约数，greatest common divisor,简称gcd。
对于非负整数x与y的最大公约数，为最大的正整数z，使得x与y均是z的整数倍。特定地，gcd(0,0)=0,gcd(0,x)=x.
小J非常清楚一点：gcd是数学王国的统治者，一切函数都要臣服于gcd之下，哪怕是增长速度极快的指数函数也不例外。
小J非常想知道当统治者gcd与速度之王结合在一起会是怎么样的效果，于是小J想出了这么一个题目：求解gcd(a^b,c^d).
小J于是将问题交给了你。为了运算方便，将最后的结果对〖10〗^9+7取模后输出。
对于30%的数据，a,b,c,d<=10.
对于60%的数据，a,b,c,d<=10000.
对于100%的数据，a,b,c,d<=10^9.
输入格式
一行四个非负整数a,b,c,d。意义见体面。
输出格式
一行一个整数，为所求的答案
输入样例
2 3 4 1
输出样例
4
题解(Gcd+分解质因数+快速幂)
也很水，先求Gcd，然后分解质因数，然后快速幂完事。还有各种特判。
其实本质就是根据Gcd定义求Gcd罢了。
数据很水，一开始没有分解质因数都能过。。。
吃饭的时候想起了分解质因数要
有没有人注意到小JJ如此爱党啊
代码
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#define Mod 1000000007
using namespace std;
typedef long long LL;
LL a, b, c, d, ans = 1ll;
LL Pow(LL x, LL n){
LL res = 1ll;
while(n){
if(n & 1) res = res * x % Mod;
x = ((x % Mod) * (x % Mod)) % Mod;
n >>= 1;
}
return res;
}
LL Gcd(LL a, LL b){
return (!b) ? a : Gcd(b, a % b);
}
int main(){
scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
if(!a && !c){
printf("0\n");
return 0;
}
if(!a){
printf("%lld\n", Pow(c, d));
return 0;
}
if(!c){
printf("%lld\n", Pow(a, b));
return 0;
}
LL g = Gcd(a, c);
if(g == 1){
printf("1\n");
return 0;
}
for(LL i = 2; i * i <= g; i++){
if(g % i == 0){
LL cnt1 = 0, cnt2 = 0;
while(a % i == 0){
cnt1 ++;
a /= i;
}
while(c % i == 0){
cnt2 ++;
c /= i;
}
ans = ans * Pow(i, min(cnt1 * b, cnt2 * d)) % Mod;
}
while(g % i == 0) g /= i;
}
if(g != 1){
LL cnt1 = 0, cnt2 = 0;
while(a % g == 0){
cnt1 ++;
a /= g;
}
while(c % g == 0){
cnt2 ++;
c /= g;
}
ans = ans * Pow(g, min(cnt1 * b, cnt2 * d)) % Mod;
}
printf("%lld\n", ans);
return 0;
}小J的网红之路
题目描述
小J在网上发现很多人都喜欢打出hhhh……h的句子。
聪明的小J观察一段时间并思考了一番之后发现，这些句子有各种各样的不同含义，哪怕是长度相同的hhhh串都可能会有不同的意思。小J意识到这是一个可以令他闻名网络世界，成为一代网红的好方法。
于是，小J打算给hhhh串编一个翻译系统。
首先，我们需要一本词典。
小J通过分析，得到了一本有m个单词的词典。对于第i个单词，由ai个h组成。注意，不会出现相同数目的h组成的单词。
进一步，我们需要找到一个语法。
小J发现语法总共有e种，每一种语法可以用(a,b,c)表示，表示如果连续三个单词依次为a、b、c，则符合该语法。保证没有相同的语法。
那么，小J实际上就是需要去解读一个长度为n的hhhh串，使得符合尽量多次语法，我们的问题就是要求出符合的语法的最大次数（同一个语法可以在不同位置被符合多次,可以重叠）。如果无法解读，输出-1.
对于30%的数据，n,m,e,ai<=10.
对于60%的数据，n,ai<=1000,m<=50,e<=100.
对于100%的数据，n,m,ai<=1000,e<=100.
输入格式
第一行为三个正整数n,m,e。意义见题面。
接下来m行每行一个正整数ai。意义见题面。
接下来e行，每行三个正整数a,b,c。(a,b,c)为对应的语法。保证1<=a,b,c<=m.
输出格式
一行一个整数，为符合的最大次数。如果无法解读，输出-1.
输入样例
4 1 1
1
1 1 1
输出样例
2
题解(dp)
这题好多人看错题，当成一个sb贪心计数去做，结果集体送命。
本人初次得分10分。
后来别人告诉我正确题意后，我想了想，发现这题的dp也不算难。
先讲正确题意（错误的不讲，太sb了），文章(句子)是由单词组成的，能否解读就是单词能否组成文章，与语法无关。这是-1的情况，用一个背包解决(然而好像不用写背包也能过)。而0是文章能用单词组成但不一定符合任何语法。要注意区分-1与0。
然后就是个
题目还有一个坑点，就是有些地方不用语法匹配也是行的，所以不匹配但合法的前提就是能解读(背包判断)，不过我们发现中间空一段不用语法匹配，或者最后不匹配前面匹配等等，相对位置不重要，因为文章都是h组成的，所以是等价的。所以取答案直接最后在n这里取都是可以的(中间的dp状态可以不用)。然后此题就BB完了。
讲个笑话，代码过不了，找别人看了半天，一直改我dp，最后发现dp没错，错误竟然是读入的是编号，没有转成单词长度(这样都有80分。。)。
代码
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#define N 1010
#define E 110
#define oo 1e9
using namespace std;
int n, m, e;
int a[N], x[N], y[N], z[N], ans = -1;
int f[N][E];
int main(){
scanf("%d%d%d", &n, &m, &e);
for(int i = 1; i <= m; i++)
scanf("%d", &a[i]);
for(int i = 1; i <= e; i++){
scanf("%d%d%d", &x[i], &y[i], &z[i]);
x[i] = a[x[i]];
y[i] = a[y[i]];
z[i] = a[z[i]];
}
memset(f, -1, sizeof(f));
f[0][0] = 0;
for(int i = 1; i <= m; i++)
for(int j = a[i]; j <= n; j++)
f[j][0] = max(f[j][0], f[j-a[i]][0]);
for(int i = 1; i <= n; i++) ans = max(ans, f[i][0]);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= e; j++){
if(i < x[j]+y[j]+z[j]) continue;
for(int k = 0; k <= e; k++){
if(z[k] == y[j] && y[k] == x[j] && ~f[i-z[j]][k]) f[i][j] = max(f[i][j], f[i-z[j]][k]+1);
if(z[k] == x[j] && ~f[i-z[j]-y[j]][k]) f[i][j] = max(f[i][j], f[i-z[j]-y[j]][k]+1);
if(~f[i-z[j]-y[j]-x[j]][k]) f[i][j] = max(f[i][j], f[i-z[j]-y[j]-x[j]][k]+1);
}
ans = max(ans, f[i][j]);
}
if(f[n][0] == -1) printf("-1\n");
else printf("%d\n", ans);
return 0;
}总结
这次三道水题，但依旧考得很差，主要因为该死的map和第三题的题意，对简单dp的掌握也没有想象中那么好。希望运气不要太差。
等到黑夜翻面之后，会是新的白昼。
——《裂缝中的阳光》