P1010 [NOIP1998 普及组] 幂次方

P1010 [ 普及组] 幂次方

#include 
using namespace std;
#define INF 0x3f3f3f3f
typedef long long LL;
const int N = 2e4 + 10;
int n;void fun(int n) {int k = n;int u = 0, idx = 0;int h[N];while(k){if(k & 1) h[++ u] = idx;k >>= 1;idx ++;}//idx显示的是右往左第idx个1位置 //eg:10 的二进制1010   2^3(这个3要化为二进制表现形式)+2^1 while(u){if(h[u] < 3){//判断最后一个进来的所在位置 if((h[u] == 0 || h[u] == 2) && u != 1) printf("2(%d)+", h[u]);else if(h[u] == 0 || h[u] == 2) printf("2(%d)", h[u]);if(h[u] == 1 && u != 1) printf("2+");else if(h[u] == 1) printf("2");-- u;}else{printf("2(");fun(h[u -- ]);//将2(?)的?改为二进制形式 if(u != 0) printf(")+");else printf(")");}}}
int main(){cin >> n;fun(n);return 0; 
} 

P1480 A/B

难绷，模板题但是我r不是 被wa了一个

#include
using namespace std;
typedef long long LL;
string a;
int B;
vector  A;
vector  div(vector  &A, int B, LL &r){vector  C;r = 0;for(int i = A.size() - 1; i >= 0; i -- ){r = r * 10 + A[i];C.push_back(r / B);r %= B;}reverse(C.begin(), C.end());while(C.size() > 1 && C.back() ==0)C.pop_back();return C;
}int main(){cin >> a >> B;for(int i = a.size() - 1; i >= 0; i -- )A.push_back(a[i] - '0');LL r;vector C = div(A, B, r);for(int i = C.size() - 1; i >= 0; i -- )cout << C[i];return 0;
} 

P1042 [ 普及组] 乒乓球

#include
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
char str[N];
int cnt = 0;
void fun(int n){int a =0, b = 0;for(int i = 0; i < cnt; i ++ ){if(str[i] == 'W') a ++ ;if(str[i] == 'L') b ++ ;if((a >= n || b >= n) && abs(a - b) >= 2){cout << a << ":" << b << endl;a = 0, b = 0;}}cout << a << ":" << b << endl;
}
int main(){char ch;while(cin >> ch && ch != 'E'){if(ch == 'W' || ch == 'L') str[cnt ++ ] = ch;}fun(11);puts("");fun(21);return 0;
}

P1563 [ 提高组] 玩具谜题

#include
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
struct stu{bool ori;string name;
}st[N];
int main(){cin >> n >> m;for(int i = 0; i < n; i ++ ) cin >> st[i].ori >> st[i].name;int pos = 0;while(m -- ){bool orie;int num;cin >> orie >> num;bool t = st[pos].ori ^ orie;if(t) pos = (pos + num) % n;else pos = ((pos - num) % n + n) %n;//pos = (pos - s + n) % n;}cout << st[pos].name << endl;return 0;
}

P2615 [ 提高组] 神奇的幻方

学了个罗伯法，简单了解了一下巴舍法

暴力模拟

#include
using namespace std;
typedef long long LL;
const int N = 40;
int n;
int a[N][N];
int main(){cin >> n;int pos = 2;int x = 1, y = (n + 1) / 2;a[x][y] = 1;for(int i = 2; i <= n * n; ++ i ){if(x == 1 && y != n){a[n][y + 1] = pos;x = n;y += 1;pos ++ ;}else if(x != 1 && y == n){a[x - 1][1] = pos;x -= 1;y = 1;pos ++ ;}else if(x == 1 && y == n){a[x + 1][y] = pos;x += 1;pos ++ ;}else{if(a[x - 1][y + 1] == 0){a[x - 1][y + 1] = pos;x -= 1;y += 1;pos ++ ;}else{a[x + 1][y] = pos;x += 1;pos ++ ;}}}for(int i = 1; i <= n; ++ i ){for(int j = 1; j <= n; ++ j ){cout << a[i][j] << " ";}puts("");}return 0;
}

罗伯法（楼梯法）

构造一个三阶幻方，首先建立一个3×3的矩阵，然后按照以下口诀填数。

一居上行正中央，

依次斜填切莫忘，

上出框界往下写，

右出框时左边放，

重复便在下格填，

出角重复一个样。

口诀释义如下：

综上，罗伯法适用于奇数阶幻方，最适合于连续自然数，但对一个等差数列则要求记住九个数字的顺序，否则容易出错。作为构造幻方的一种经典方法，自当学习和掌握之。

#include
using namespace std;
typedef long long LL;
const int N = 40;
int n;
int a[N][N];
int main(){cin >> n;int pos = 1;int x = 1, y = (n + 1) / 2;a[x][y] = 1;while(pos < n * n){pos ++ ;x -- , y ++ ;if(x <= 0) x = n;if(x > n) x = 1;if(y <= 0) y = n;if(y > n) y = 1;if(a[x][y]){if((x + 2) > n) x = (x + 2) - n; //6->4重复 else x += 2; // 3->1重复if(y <= 1) y = n; //6->4重复// 这个地方 y += 2 就只有20分了 else y -- ; // 3->1重复 }a[x][y] = pos;}	for(int i = 1; i <= n; ++ i ){for(int j = 1; j <= n; ++ j ){cout << a[i][j] << " ";}puts("");}return 0;
}

二、巴舍法（“平移补空法”）

巨佬写的orz

#include
using namespace std;
typedef long long LL;
const int N = 40;
int n;
int a[N][N];
int main(){cin >> n;int pos = 1;int x = 1, y = (n + 1) / 2;for(int i = 1; i <= n * n; i ++ ){a[x][y] = i;if(!a[(x - 2 + n) % n + 1][y % n + 1]) x = (x - 2 + n) % n + 1, y = y % n + 1;else x = x % n + 1;}for(int i = 1; i <= n; ++ i ){for(int j = 1; j <= n; ++ j ){cout << a[i][j] << " ";}puts("");}return 0;
}

P1024 [ 提高组] 一元三次方程求解

这题坑有点多，实数a,b,c,d要用，精度值应在要求的多一位

使用勘根定理以及二分来写

#include
using namespace std;
typedef long long LL;
double a, b, c, d;
double fun(double x){return a * x * x * x + b * x * x + c * x + d;
}
int main(){double l, r, mid, f1, f2;int cnt = 0;cin >> a >> b >> c >> d;for (int i = -100; i < 100; i ++ ){l = i; r = i + 1;f1 = fun(l); f2 = fun(r);if(!f1) {printf("%.2lf ", l); cnt ++ ;}if(f1 * f2 < 0) {while(r - l >= 0.001) {mid = (l + r) / 2; if(fun(mid) * fun(r) <= 0) l = mid; else r = mid;  }printf("%.2lf ", r);  cnt ++ ;}if(cnt == 3) break;             }return 0;
}

woc重刷的时候居然卡在了fun函数我给的是int型，我nt吧ORZ

P3612 [] Cow Code S 题解

这题我一开始题目都有点蒙，完全没啥思路。

将旋转三次的以及不旋转直接复制三次的拿来对比

旋转三次：

复制三次：

第四个是又第三个变的巴拉巴拉，设串长为L，初始字符为

, 但又因为旋转的规则是将最后一个放最前再去复制前缀，所以初始字符位置应该是

.

这道题第二次做也没想出来很好的思路，

#include
using namespace std;
typedef long long LL;
string s;
LL n;
int main(){cin >> s >> n;LL num = s.size();while(num < n){LL i = num;while(n > i) i *= 2;i /= 2;n -= (i + 1);if(n == 0) n = i;}cout << s[n - 1] << endl;return 0;
} 

P3742 umi的函数

既然是构造一个符合条件的z，那当y不取z中的字母就表示z[i] 比x[i]大，那直接取最大的z来构造呗（注意如果这样char型所求就不能命名为z，换个字母就行

当然直接就令z[i]比x[i]大1也是OK的

不能用，一定要char （但大佬的方法的话用也能过TAT

#include
using namespace std;
typedef long long LL;
int n;
char x[110], y[110], t[110];
int main(){cin >> n >> x >> y;for(int i = 0; i < n; i ++ ){if(x[i] < y[i]){cout << -1 << endl;return 0;}if(x[i] > y[i]) t[i] = y[i];else t[i] = 'z';}cout << t;return 0;
}

看了大佬的题解，被dalao一句“因为Y本身就是Z的一种解”给干废了QAQ

附上大佬的代码，给后面复习的自己%%%一下orz

----

二刷的时候有思路了

哥们球球你记住，放局部多开的会被随机赋值的

#include
using namespace std;
typedef long long LL;
int n;
char x[110], y[110];
int main(){cin >> n >> x >> y;for(int i = 0; i < n; i ++ ){if(x[i] < y[i]){cout << -1;return 0;}}cout << y;return 0;
}

P1009 [ 普及组] 阶乘之和

加和乘法之间的逻辑顺序没有理清。。。。>= r ，l 和 r都符合恰好位于临界点mid的条件，可以输出 r 作为答案。

这题本质的模板就是求临界的最大值（

然后二刷的时候发现一刷写的循环时有点小bug（虽然ac了）

#include 
using namespace std;
#define INF 0x3f3f3f3f
#define x first
#define y second
#define mod 7
typedef long long LL;
const int N = 5e4 + 10;
int L, n, m;
int d[N];
int check(int mid){int last = 0, cnt = 0;for(int i = 1; i <= n; i ++ ){if(d[i] - last < mid) cnt ++ ;else last = d[i];}return cnt <= m;
}
int main(){cin >> L >> n >> m;for(int i = 1; i <= n; i ++ ) cin >> d[i];d[++ n] = L;int l = 1, r = L;while(l < r){int mid = l + r + 1 >> 1;if(check(mid)) l = mid;else r = mid - 1;}cout << r << endl;return 0;
}

P4995 跳跳！

双指针做法写是写出来了，但是问题是巨佬的解法好牛，记录一下

#include
using namespace std;
typedef long long LL;
const int N = 1e4 + 10;
LL ans;
int h[N];
int n;
bool sum;
int main(){cin >> n; for(int i = 1; i <= n; i ++ ) cin >> h[i];sort(h + 1, h + 1 + n);int j = 0, hpast = 0;for(int i = 1; i <= n; i ++ ){j = n - j + sum;sum = !sum;ans += pow(h[j] - hpast, 2);hpast = h[j];}cout << ans;return 0;
}

P2280 []激光炸弹

这里的n是指目标的个数，但不是这个棋盘的面积！！！

二刷：这道题有个小坑又踩了一下，就是其实题目没有告诉矩形的边长各是多少，如果按照开的数组N答案就是错误的，由于矩形我们已知最大取5000，但在写的时候为了防止越界，要把横纵坐标都加一，所以矩形最大范围应该是5001.

不过如果在输入时就将矩形边长计入统计，就不会踩我上面地方坑了QAQ

#include 
using namespace std;
typedef long long LL; 
int n, m;
const int N = 5010;
int ans;
int s[N][N];
int main(){cin >> n >> m;for(int i = 1; i <= n; i ++ ){int x, y, v;cin >> x >> y >> v;s[x + 1][y + 1] += v;}for(int i = 1; i <= 5001; i ++ ){for(int j = 1; j <= 5001; j ++ ){s[i][j] +=  s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];}}for(int i = m; i <= 5001; i ++ ){for(int j = m; j <= 5001; j ++ ){ans = max(ans, s[i][j] - s[i -m][j] - s[i][j - m] + s[i - m][j - m]) ;}}cout << ans;return 0;
}

P1996 约瑟夫问题

对队列queue的使用不熟悉

二刷思路还是有点钝

#include 
using namespace std;
typedef long long LL;
int n, m;
queue qu;
int main(){cin >> n >> m;int cnt = 1;for(int i = 1; i <= n; i ++ ){qu.push(i);}while(!qu.empty()){if(cnt == m){cout << qu.front() << " ";qu.pop();cnt = 1;}else{cnt ++;qu.push(qu.front());qu.pop();}}return 0;
}