题意：找到[a, b]的最大公约数；
思路：相同时为本身，不同时为1.
套路：碰到水题别想太多；
猜想：两个相邻数，必有一奇一偶，如果偶数有因子3或者其他，奇数可不可能有相同的呢？
枚举一些数后发现没有，出现的奇数全是素数。
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set> #define c_false ios_base::sync_with_stdio(false); cin.tie(0)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define zero_(x,y) memset(x , y , sizeof(x))
#define zero(x) memset(x , 0 , sizeof(x))
#define MAX(x) memset(x , 0x3f ,sizeof(x))
#define swa(x,y) {LL s;s=x;x=y;y=s;}
using namespace std ;
typedef long long LL;
const int N = ; char n[N], m[N]; int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//ios_base::sync_with_stdio(false); cin.tie(0);
scanf("%s%s", n, m);
string n1, m1;
n1 = n; m1 = m;
if(n1 == m1) printf("%s\n", n);
else printf("1\n");
return ;
}
题意：找到一些数，满足以下等式 ：？+ ？ + ？- ？ = n
思路：1) 可以将+ 和 - 分开计算，+ sum1, - sum2 然后将sum1 与sum 2 分派下去，
2) (注意到数是可以重复的) 先将所有数设置为1， 然后 ans > n, - 加1，否则 + 加1；
1 #include <iostream>
2 #include <algorithm>
3 #include <stdlib.h>
4 #include <time.h>
5 #include <cmath>
6 #include <cstdio>
7 #include <string>
8 #include <cstring>
9 #include <vector>
10 #include <queue>
11 #include <stack>
12 #include <set>
13
14 #define c_false ios_base::sync_with_stdio(false); cin.tie(0)
15 #define INF 0x3f3f3f3f
16 #define INFL 0x3f3f3f3f3f3f3f3f
17 #define zero_(x,y) memset(x , y , sizeof(x))
18 #define zero(x) memset(x , 0 , sizeof(x))
19 #define MAX(x) memset(x , 0x3f ,sizeof(x))
20 #define swa(x,y) {LL s;s=x;x=y;y=s;}
21 using namespace std ;
22 typedef long long LL;
23 const int N = 205;
24
25 int num1[N], num2[N];
26 char s[2];
27
28 int main(){
29 //freopen("in.txt","r",stdin);
30 //freopen("out.txt","w",stdout);
31 //ios_base::sync_with_stdio(false); cin.tie(0);
32 zero(num1);
33 zero(num2);
34 scanf("%s", s);
35 scanf("%s", s);
36 int p = 1, q = 0, k = 1;
37 num1[1] = 1;
38 while(s[0] != '='){
39 if(s[0] == '+'){
40 num1[++k] = 1;
41 p++;
42 }
43 if(s[0] == '-'){
44 num1[++k] = -1;
45 q++;
46 }
47 scanf("%s", s);
48 scanf("%s", s);
49 }
50 int n;
51 scanf("%d", &n);
52 for(int i = 1; i <= k; i++){
53 num2[i] = 1;
54 }
55 int sum = p - q;
56 for(int i = 1; i <= k; i++){
57 while(sum < n && num1[i] == 1 && num2[i] < n){
58 num2[i]++, sum++;
59 }
60 while(sum > n && num1[i] == -1 && num2[i] < n){
61 num2[i]++, sum--;
62 }
63 }
64 if(sum != n){
65 printf("Impossible\n");
66 return 0;
67 }
68 printf("Possible\n");
69 printf("%d ", num2[1]);
70 for(int i = 2; i <= k; i++){
71 if(num1[i] == 1) printf("+ ");
72 else if(num1[i] == -1) printf("- ");
73 printf("%d ", num2[i]);
74 }
75 printf("= %d\n", n);
76 return 0;
77 }
C：
题意：求尾号代表的年份
思路：贪心法， 主要是如何通过后缀找到原年份。
区间的长度为后缀字符的个数^10
可以先预处理区间长度再找后缀字符的位置；
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set> #define c_false ios_base::sync_with_stdio(false); cin.tie(0)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define zero_(x,y) memset(x , y , sizeof(x))
#define zero(x) memset(x , 0 , sizeof(x))
#define MAX(x) memset(x , 0x3f ,sizeof(x))
#define swa(x,y) {LL s;s=x;x=y;y=s;}
using namespace std;
typedef long long LL;
const int N = ; LL a[], a1[];
char b[]; int Solve(){
int len = strlen(b);
LL num = ;
for(int i = ; i < len; i++){
num *= ;
num += b[i] - '';
}
for(int i = ; i < ; i++){
int number = num + (LL)i * a1[len-];
if(number >= a[len-] && number < a[len - ]){
printf("%d\n", number);
return ;
}
}
return ;
} int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//ios_base::sync_with_stdio(false); cin.tie(0);
int n, k = ;
a[] = ;
a1[] = ;
//设置首位置
for(int i = ; i < ; i++){
k *= ;
a[i] = a[i-] + k;
a1[i] = k;
}
scanf("%d", &n);
while(n--){
scanf("%s", b);
//printf("%s\n", b);
Solve();
}
return ;
}
D：
题意：将一些点翻转过来，得到所有边都相同颜色的图
思路：暴力美学，dfs搜索