龟速乘
主要解决大数相乘爆long long（有模数
思维和快速幂相似
ll qpow(ll n, ll k, ll p) {
ll res = 0;
while(k) {
if(k & 1) res = (res + n + p) % p;
n = (n + n) % p;
k >>= 1;
}
return res;
}
递推
25 盏灯排成一个 5×5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
可以确定第一行的状态来确定其他所有的状态，所以只需要枚举第一行的状态，就好了
（降低复杂度）
const int MAX = 1e5 + 10;
// 第一行确定就所有的都确定了，好妙
// 有些时候状态不重要，有没有操作才重要
char a[6][6];
int dx[] = {0, 1, -1, 0, 0};
int dy[] = {0, 0, 0, 1, -1};
void turn(int x, int y) {
for(int i = 0; i < 5; i++) {
int tx = x + dx[i];
int ty = y + dy[i];
if(tx >= 0 && tx < 5 && ty >= 0 && ty < 5) {
a[tx][ty] ^= 1;
}
}
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
char bf[6][6];
for(int i = 0; i < 5; i++) {
scanf("%s", bf[i]);
}
int ans = -1;
for(int tai = 0; tai < 32; tai++) {//每个状态
memcpy (a, bf, sizeof a);
int step = 0;
for(int i = 0; i < 5; i++) {
if(tai >> i & 1) {
step++;
turn(0, i);
}
}
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 5; j++) {
if(a[i][j] == '0') {
turn(i, j + 1);
step++;
}
}
}
bool flag = 1;
for(int i = 0; i < 5; i++) {
if(a[4][i] == '0') {
flag = 0;
break;
}
}
if(flag == 0 || step > 6) {
continue;
}
ans = min(ans, step);
}
printf("%d\n", ans);
}
}
约数的另一个求法（递归
可以有效避免模数可能与其不互质的情况
原理是偶数项数是，后一半可以提取$p^{k/2}$，奇数项数，可以撇开第一项，其他项提取p，变成偶数项数的情况
（代码中k从0开始，所以k的奇偶与项数的奇偶相反
const int mod = 9901;
ll qpow(ll n, ll k) {
ll res = 1;
while (k) {
if (k & 1) res = (res * n) % mod;
k >>= 1;
n = (n * n) % mod;
}
return res;
}
ll sum(ll p, ll k) {
if (k == 0) return 1;
if (k % 2 == 0) return (1 + p % mod * sum(p, k - 1)) % mod;
if (k % 2) return (1 + qpow(p, k / 2 + 1)) * sum(p, k / 2) % mod;
}
int main() {
int A, B;
scanf("%d%d", &A, &B);
ll res = 1;
for (int i = 2; i <= A / i; i++) {
int tmp = 0;
while (A % i == 0) {
A /= i;
tmp++;
}
res = (res * (sum(i, tmp * B))) % mod;
}
if (A != 1) res = (res * sum(A, B)) % mod;
if (A == 0) res = 0;
printf("%lld\n", res);
}
分形之城
一个很好的递归题，重点是坐标系的规定，以及由小到大的变换
激光炸弹
二维差分,求前缀的操作如下
a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + a[i][j];
增减序列
一道思维性（需要记住方法的）的前后缀转化，求解问题
最佳牛围栏
多校有一道原题（只不过多校题要求两次）
重点是想到二分，以后多一个联想 平均值/最大最小值==>二分
区间长度大于F的，问连续区间的平均值最大
const int MAX = 1e5 + 10;
const double eps = 1e-4;
double sum[MAX];
double a[MAX];
int n, m;
bool check ( double avg ) {
for ( int i = 1; i <= n; i++ ) {
sum[i] = sum[i - 1] + a[i] - avg;
}
double minn = 0;
for ( int i = 0, j = m; j <= n; i++, j++ ) {
minn = min ( minn, sum[i] );
if ( sum[j] - minn >= 0 ) return 1;
}
return 0;
}
//最大值
int main() {
scanf ( "%d%d", &n, &m );
double L = 0, R = -1;
for ( int i = 1; i <= n; i++ ) {
scanf ( "%lf", &a[i] );
R = max ( R, a[i] );
}
while ( R - L > eps ) {
double mid = ( L + R ) / 2;
if ( check ( mid ) ) L = mid;
else R = mid;
}
printf ( "%d\n", (int)(R * 1000) );
}
七夕祭
某个点可以上移下移，问是否可以做到每行每列的点数相同，第一列和最后一列连接，使得最小交换次数
首先确定每行每列可以单独考虑
然后就是均分纸牌问题
均分纸牌的思路：目标是把所有的点的值变成均值x，那不整除的一定不可以
如果考虑从前往后分，每个点可以往后分$(a_i - x)$,复数相当于后面给前面，显然不考虑顺序的话，是可以的
可以先预处理把$a_i$变成$(a_i - x)$，那任意考虑一个位置pos，相当于前面多的少的给他了，即这个点的需要移动$(\sum_{i = 0}^{pos-1}(a_i - x))=sum[pos]$的值
回到本问题：问题是使得交换次数最少，而首位相连，每个点都是等同的，那就找一个中值，因为答案相加的绝对值
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 2e5 + 100;
int n, m;
ll sum[MAX];
ll a[MAX];
ll b[MAX];
int get(ll *a, int n) {
ll ans = 0;
for(int i = 1; i <= n; i++) {
ans += a[i];
}
ans /= n;
for(int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + a[i] - ans;
}
sort(sum + 1, sum + 1 + n);
ll res = 0;
int mid = sum[n / 2 + 1];
for(int i = 1; i <= n; i++) {
res += abs(sum[i] - mid);
}
return res;
}
int main() {
int T;
scanf("%d%d%d", &n, &m, &T);
int TT = T;//有T个坐标，坐标上有点
while(TT--) {
int l, r;
scanf("%d%d", &l, &r);
a[l]++, b[r]++;
}
if (T % n && T % m) {
puts("impossible");
} else if (T % n) {
printf("column %lld", get(b, m));
} else if (T % m) {
printf("row %lld", get(a, n));
} else {
printf("both %lld", get(a, n) + get(b, m));
}
}
动态中位数
给n个数，输出第偶数位的中位数
两个优先队列优化；不难，就是需要想到
typedef long long ll;
const int MAX = 2e5 + 100;
int main() {
int T;
scanf("%d", &T);
while(T--) {
int id, n;
scanf("%d%d", &id, &n);
printf("%d %d\n", id, n + 1 >> 1);
priority_queue<int> up;
priority_queue<int, vector<int>, greater<int> > down;
int cnt = 0;
for(int i = 1; i <= n; i++) {
int x;scanf("%d", &x);
if(down.empty() || x >= down.top()) down.push(x);
else up.push(x);
while(up.size() >= 1 + down.size()) {
down.push(up.top());
up.pop();
}
while(up.size() + 2 <= down.size()) {
up.push(down.top());
down.pop();
}
if(i % 2 == 1) {
printf("%d ", down.top());
cnt++;
if(cnt % 10 == 0 && cnt != 0) printf("\n");
}
}
if(cnt % 10 != 0)
printf("\n");
}
}
超快速排序
求逆序对，我用的是树状数组
天才的记忆
问区间的最大值
typedef long long ll;
const int MAX = 2e5 + 100;
int a[MAX];
int dp[MAX][19];
void init(int n) {
for(int j = 0; j < 18; j++) {
for(int i = 1; i + (1 << (max(1, j) - 1)) <= n; i++) {
if(j == 0) dp[i][j] = a[i];
else dp[i][j] = max(dp[i + (1 << (j - 1))][j - 1], dp[i][j - 1]);
}
}
}
int main() {
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
init(n);
int q;
scanf("%d", &q);
while(q--) {
int l, r;
scanf("%d%d", &l, &r);
int len = log(r - l + 1) / log(2);
int ans = max(dp[l][len], dp[r - (1 << len) + 1][len]);
printf("%d\n", ans);
}
}
