给一堆围成圈的小朋友发饼干，小朋友为1~n号，第几号小朋友每次拿多少块饼干，问最后剩多少饼干
#include <iostream> #include <cstdio> using namespace std; int main() { // freopen("a.in" , "r" , stdin); int n , m; while(scanf("%d%d" , &n , &m) == 2) { int tmp = (1 + n ) * n / 2; m %= tmp; for(int i=1 ; i<=n ; i++){ if(m >= i) m-=i; else break; } printf("%d " , m); } return 0; }
用0，1分别代表己方和对方球员，如果有7个及以上的同队队员站一起会危险，问是否处于危险状态
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int N = 105; char s[N]; int pos[N]; int main() { // freopen("a.in" , "r" , stdin); while(scanf("%s" , s) != EOF) { int len = strlen(s); for(int i=0 ; i<len ; i++){ if(s[i] == '0') pos[i] = 0; else pos[i] = 1; } int flag = pos[0] , cnt = 1; bool ok = true; for(int i=1 ; i<len ; i++){ if(pos[i] == flag){ cnt++; if(cnt >= 7){ ok = false; break; } } else{ flag = pos[i]; cnt = 1; } } if(ok) puts("NO"); else puts("YES"); } return 0; }
将字符串按某种规则缩写
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int N = 105; char s[N]; int main() { // freopen("a.in" , "r" , stdin); int T; scanf("%d" , &T); while(T--) { scanf("%s" , s); int len = strlen(s); if(len <= 10){ printf("%s " , s); continue; } printf("%c%d%c " , s[0] , len-2, s[len-1]); } return 0; }
枚举所有可能的值就可以了
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int N = 105; int val[N]; int main() { // freopen("a.in" , "r" , stdin); int n , k , t; while(scanf("%d%d%d" , &n , &k , &t) == 3) { int tmp = k*n*t , p , q; memset(val , 0 , sizeof(val)); for(p=0 ; p<=n ; p++){ int flag = 0; for(q=0 ; q<=k ; q++){ int tmp1 = 100*p*k + 100 * q; // cout<<"tmp: "<<tmp<<" "<<tmp1<<endl; if(tmp >= tmp1 && tmp<tmp1+100){ flag= 1; break; } } if(flag) break; } // cout<<p<<" "<<q<<endl; for(int i=1 ; i<=p ; i++) val[i] = k; val[p+1] = q; for(int i=1 ; i<=n ; i++) if(i == 1) printf("%d" , val[i]); else printf(" %d" ,val[i]); puts(""); } return 0; }
枚举所有的因子，然后令每个数都对这个因子取模，观察模相同的数是否等于总数除以因子
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; const int N = 100005; int vis[N] , mul[N] , cnt , a[N] , tot[N]; void cal(int n) { int t = (int)sqrt(n); cnt = 0; if(n % 4==0){ mul[cnt++] = 4; } while(n % 2 == 0) n>>=1; for(int i=3 ; i<=t ; i++){ if(n % i == 0){ mul[cnt++] = i; while(n % i == 0)n/=i; } if(i > n) break; } if(n>1) mul[cnt++] = n; } int main() { // freopen("a.in" , "r" , stdin); int n , x; while(~scanf("%d" , &n)) { int k=0; for(int i=0 ; i< n;i++){ scanf("%d" , &x); if(x == 1) a[k++] = i; } cal(n); int flag = 0; for(int i=0 ; i<cnt ; i++) { int tmp = n/mul[i]; memset(tot , 0 , sizeof(tot)); for(int j=0 ; j<k ; j++){ int pp = a[j] % tmp; tot[pp] ++; if(tot[pp] == mul[i]){ flag = 1; break; } } if(flag) break; } if(flag) puts("YES"); else puts("NO"); } return 0; }
纯模拟，代码量略长
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 60; char str[4]; int num[N][N] , vis[N]; int cnt; //记录可行矩阵的个数 struct Node{ int x,y; }node[60]; Node pos1 , pos2; Node squre1 , squre2; int change1(char c) { if(c == 'C') return 0; else if(c == 'D') return 1; else if(c == 'H') return 2; else if(c == 'S') return 3; } int change2(char c) { if(c == 'A') return 0; else if(c == 'T') return 9; else if(c == 'J') return 10; else if(c == 'Q') return 11; else if(c == 'K') return 12; else { return (int)(c-'1'); } } bool ok(int i , int j) { int flag1 = 1 , flag2 = 1; int mod[20]; memset(mod, 0 , sizeof(mod)); for(int p=0 ; p<3 ; p++){ for(int q=0 ; q<3 ; q++){ int t = num[i+p][j+q] % 13; if(mod[t]){ flag1 = 0; break; } mod[t] = 1; } if(!flag1) break; } if(flag1) return true; int col = num[i][j] / 13; for(int p=0 ; p<3 ; p++){ for(int q=0 ; q<3 ; q++){ int t = num[i+p][j+q] / 13; if(t != col){ flag2 = 0; break; } } if(!flag2) break; } if(flag2) return true; else return false; } bool ok1(Node m1 , Node m2) { if(m1.x > m2.x+2) return true; if(m1.x+2 < m2.x) return true; if(m1.y+2 < m2.y) return true; if(m1.y > m2.y+2) return true; return false; } void get_martrix(int n , int m) { cnt = 0; for(int i=1 ; i<=n-2 ; i++){ for(int j=1 ; j<=m-2 ; j++){ if(ok(i,j)){ node[cnt].x = i; node[cnt++].y = j; } } } } char* intTostring(int x) { char *s = new char [3]; int t1 = x/13; if(t1 == 0) s[1] = 'C'; else if(t1 == 1) s[1] = 'D'; else if(t1 == 2) s[1] = 'H'; else if(t1 == 3) s[1] = 'S'; int t2 = x%13; if(t2 == 0) s[0] = 'A'; else if(t2 == 9) s[0] = 'T'; else if(t2 == 10) s[0] = 'J'; else if(t2 == 11) s[0] = 'Q'; else if(t2 == 12) s[0] = 'K'; else { s[0] = (char)(t2+'1'); } s[2] = ' '; return s; } int main() { // freopen("a.in" , "r" , stdin); int n , m; while(scanf("%d%d" , &n , &m) == 2) { bool flag1 = false , flag2 = false; int ans1 , ans2 , card1 , card2;//记录最后选中的在第几号节点 pos1.x = pos1.y = pos2.x = pos2.y = 0; memset(vis , 0 , sizeof(vis)); for(int i=1 ; i<=n ; i++) for(int j = 1 ; j<=m ; j++) { scanf("%s" , str); if(str[1] == '1'){ pos1.x = i; pos1.y = j; flag1 = true; } else if(str[1] == '2'){ pos2.x = i; pos2.y = j; flag2 = true; } else{ num[i][j] = 13*change1(str[1]) + change2(str[0]); vis[num[i][j]] = 1; } } /* for(int i=1 ; i<=n ; i++){ for(int j = 1 ; j<=m ; j++) cout<<num[i][j]<<" "; puts(""); }*/ bool find = false; int time=0; if(flag1) time++; if(flag2) time++; for(int p=0 ; p<52 ; p++){ for(int q=0 ; q<52 ; q++){ if(p == q) continue; int change = time; if(flag1 && !vis[p]) num[pos1.x][pos1.y] = p,change--; if(flag2 && !vis[q]) num[pos2.x][pos2.y] = q,change--; if(!change) { get_martrix(n , m); for(int i=0 ; i<cnt ; i++){ for(int j=i+1 ; j<cnt ; j++){ if(ok1(node[i] , node[j])){ find=true; ans1 = i , ans2 = j; card1 = p , card2 = q; break; } } if(find) break; } } if(find) break; } if(find) break; } if(!find) puts("No solution."); else{ puts("Solution exists."); if(!flag1 && !flag2){ puts("There are no jokers."); } else if(flag1 && flag2){ char *s1 = new char [3]; char *s2 = new char [3]; s1 = intTostring(card1); s2 = intTostring(card2); printf("Replace J1 with %s and J2 with %s. " , s1 , s2); } else if(flag1){ char *s1 = new char [3]; s1 = intTostring(card1); printf("Replace J1 with %s. " , s1); } else if(flag2){ char *s1 = new char [3]; s1 = intTostring(card2); printf("Replace J2 with %s. " , s1); } printf("Put the first square to (%d, %d). " , node[ans1].x , node[ans1].y); printf("Put the second square to (%d, %d). " , node[ans2].x , node[ans2].y); } } return 0; }
一道简单的nim博弈，sg函数值的计算过程中注意保存得到的最小堆数，过程可以用异或的前缀和帮助自己提高效率
#include <cstdio> #include <cstring> #include <iostream> #include <cmath> using namespace std; const int N = 100010; int sg[N] , sum[N] , minn[N] , vis[N]; void init_sg() { sg[0] = sg[1] = sg[2] = 0; sum[0] = sum[1] = sum[2] = 0; memset(minn , 0x3f , sizeof(minn)); for(int n=3 ; n<=100000 ; n++){ int t = 2*n; int factor = (int)(sqrt(t+0.5)); for(int k=2 ; k<=factor ; k++){ if(t % k == 0 && t/k+1-k>0 && !((t/k+1-k)&1)){ int a = (t/k+1-k)/2; int p = sum[a+k-1]^sum[a-1]; vis[p] = n; if(p == 0) minn[n] = min(minn[n] , k); } } //找没有出现过的最小的sg函数 int v = 0; while(1){ if(vis[v] != n){ sg[n] = v; break; } v++; } //记录当前的sum[]前缀 sum[n] = sum[n-1]^sg[n]; } } int main() { // freopen("a.in" , "r" , stdin); init_sg(); int n; while(scanf("%d" , &n) == 1) { if(!sg[n]){ puts("-1"); continue; } printf("%d " , minn[n]); } return 0; }