目录
codeforces1080A
传送门：https://codeforces.com/contest/1080/problem/A
题意：制造一份邀请函需要2份a物品，5份b物品，8份c物品，一个盒子里面有k份物品（可以为a或b或c）问你制造n份邀请函需要用多少个盒子
题解:直接加起来就行
/**
* ┏┓ ┏┓
* ┏┛┗━━━━━━━┛┗━━━┓
* ┃ ┃
* ┃ ━ ┃
* ┃ ＞ ＜ ┃
* ┃ ┃
* ┃... ⌒ ... ┃
* ┃ ┃
* ┗━┓ ┏━┛
* ┃ ┃ Code is far away from bug with the animal protecting
* ┃ ┃ 神兽保佑,代码无bug
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┗━━━┓
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛
*/
// warm heart, wagging tail,and a smile just for you!
//
// _ooOoo_
// o8888888o
// 88" . "88
// (| -_- |)
// O\ = /O
// ____/`---'\____
// .' \| |// `.
// / \||| : |||// \
// / _||||| -:- |||||- \
// | | \\ - /// | |
// | \_| ''\---/'' | |
// \ .-\__ `-` ___/-. /
// ___`. .' /--.--\ `. . __
// ."" '< `.___\_<|>_/___.' >'"".
// | | : `- \`.;`\ _ /`;.`/ - ` : | |
// \ \ `-. \_ __\ /__ _/ .-` / /
// ======`-.____`-.___\_____/___.-`____.-'======
// `=---='
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// 佛祖保佑 永无BUG
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL;
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define bug printf("*********\n")
#define FIN freopen("input.txt","r",stdin);
#define FON freopen("output.txt","w+",stdout);
#define IO ios::sync_with_stdio(false),cin.tie(0)
#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"
#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"
#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"
const int BufferSize=1<<16;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
if(head==tail) {
int l=fread(buffer,1,BufferSize,stdin);
tail=(head=buffer)+l;
}
return *head++;
}
inline int read() {
int x=0,f=1;char c=Getchar();
for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=Getchar()) x=x*10+c-'0';
return x*f;
}
const double eps = 1e-8;
const int mod = 1e9+7;
const int maxn = 3e5 + 5;
const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3f;
int main() {
#ifndef ONLINE_JUDGE
FIN
#endif
int n,k;
scanf("%d%d",&n,&k);
LL sum1=(n*2+k-1)/k;
LL sum2=(n*5+k-1)/k;
LL sum3=(n*8+k-1)/k;
printf("%lld\n",sum1+sum2+sum3);
return 0;
}
codeforces 1080B
传送门:https://codeforces.com/contest/1080/problem/B
题意：有一个序列形如 -1 2 -3 4 -5 6这样，m次询问，问你这个序列区间 \(l,r\) 内的的和是多少
题解：用一个等差数列求和即可，或者发现相邻两项和为1，然后特判一下l的奇偶性即可
/**
* ┏┓ ┏┓
* ┏┛┗━━━━━━━┛┗━━━┓
* ┃ ┃
* ┃ ━ ┃
* ┃ ＞ ＜ ┃
* ┃ ┃
* ┃... ⌒ ... ┃
* ┃ ┃
* ┗━┓ ┏━┛
* ┃ ┃ Code is far away from bug with the animal protecting
* ┃ ┃ 神兽保佑,代码无bug
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┗━━━┓
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛
*/
// warm heart, wagging tail,and a smile just for you!
//
// _ooOoo_
// o8888888o
// 88" . "88
// (| -_- |)
// O\ = /O
// ____/`---'\____
// .' \| |// `.
// / \||| : |||// \
// / _||||| -:- |||||- \
// | | \\ - /// | |
// | \_| ''\---/'' | |
// \ .-\__ `-` ___/-. /
// ___`. .' /--.--\ `. . __
// ."" '< `.___\_<|>_/___.' >'"".
// | | : `- \`.;`\ _ /`;.`/ - ` : | |
// \ \ `-. \_ __\ /__ _/ .-` / /
// ======`-.____`-.___\_____/___.-`____.-'======
// `=---='
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// 佛祖保佑 永无BUG
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL;
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define bug printf("*********\n")
#define FIN freopen("input.txt","r",stdin);
#define FON freopen("output.txt","w+",stdout);
#define IO ios::sync_with_stdio(false),cin.tie(0)
#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"
#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"
#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"
const int BufferSize = 1 << 16;
char buffer[BufferSize], *head, *tail;
inline char Getchar() {
if(head == tail) {
int l = fread(buffer, 1, BufferSize, stdin);
tail = (head = buffer) + l;
}
return *head++;
}
inline int read() {
int x = 0, f = 1; char c = Getchar();
for(; !isdigit(c); c = Getchar()) if(c == '-') f = -1;
for(; isdigit(c); c = Getchar()) x = x * 10 + c - '0';
return x * f;
}
const double eps = 1e-8;
const int mod = 1e9 + 7;
const int maxn = 3e5 + 5;
const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3f;
int main() {
#ifndef ONLINE_JUDGE
FIN
#endif
int q;
scanf("%d", &q);
while(q--) {
LL l, r;
scanf("%lld%lld", &l, &r);
LL len = r - l + 1;
if(l % 2) {
if(len % 2) {
printf("%lld\n", len / 2 - r);
} else {
printf("%lld\n", len / 2);
}
} else {
if(len % 2) {
printf("%lld\n", r - len / 2);
} else {
printf("%lld\n", -len / 2);
}
}
}
return 0;
}
codeforces 1080C
传送门：https://codeforces.com/contest/1080/problem/C
题意：给你一个nxm的黑白棋盘，形如
现在先后进行两次操作，第一次操作矩形（x1,y1,x2,y2）内的格子变成白色，第二次操作将矩形（x3,y3,x4,y4）内的格子变成黑色，询问你这个棋盘上白色格子和黑色格子的数量
题解：矩形面积并裸题，如果两次操作的矩形有相交的部分，就将白色部分的格子减去被覆盖的部分
/**
* ┏┓ ┏┓
* ┏┛┗━━━━━━━┛┗━━━┓
* ┃ ┃
* ┃ ━ ┃
* ┃ ＞ ＜ ┃
* ┃ ┃
* ┃... ⌒ ... ┃
* ┃ ┃
* ┗━┓ ┏━┛
* ┃ ┃ Code is far away from bug with the animal protecting
* ┃ ┃ 神兽保佑,代码无bug
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┗━━━┓
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛
*/
// warm heart, wagging tail,and a smile just for you!
//
// _ooOoo_
// o8888888o
// 88" . "88
// (| -_- |)
// O\ = /O
// ____/`---'\____
// .' \| |// `.
// / \||| : |||// \
// / _||||| -:- |||||- \
// | | \\ - /// | |
// | \_| ''\---/'' | |
// \ .-\__ `-` ___/-. /
// ___`. .' /--.--\ `. . __
// ."" '< `.___\_<|>_/___.' >'"".
// | | : `- \`.;`\ _ /`;.`/ - ` : | |
// \ \ `-. \_ __\ /__ _/ .-` / /
// ======`-.____`-.___\_____/___.-`____.-'======
// `=---='
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// 佛祖保佑 永无BUG
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL;
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define bug printf("*********\n")
#define FIN freopen("input.txt","r",stdin);
#define FON freopen("output.txt","w+",stdout);
#define IO ios::sync_with_stdio(false),cin.tie(0)
#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"
#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"
#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"
const int BufferSize = 1 << 16;
char buffer[BufferSize], *head, *tail;
inline char Getchar() {
if(head == tail) {
int l = fread(buffer, 1, BufferSize, stdin);
tail = (head = buffer) + l;
}
return *head++;
}
inline int read() {
int x = 0, f = 1; char c = Getchar();
for(; !isdigit(c); c = Getchar()) if(c == '-') f = -1;
for(; isdigit(c); c = Getchar()) x = x * 10 + c - '0';
return x * f;
}
const double eps = 1e-8;
const int mod = 1e9 + 7;
const int maxn = 3e5 + 5;
const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3f;
LL n, m;
LL x1, y1, x2, y2;
LL x3, y3, x4, y4;
LL wsum, bsum;
LL get_white(LL x, LL y) {
if((x * y) % 2 == 0) return (x * y) / 2;
else {
return (x * y) / 2 + 1;
}
}
LL get_black(LL x, LL y) {
if((x * y) % 2 == 0) return (x * y) / 2;
else {
return (x * y) / 2;
}
}
LL get_rec_black(LL x1, LL y1, LL x2, LL y2) {
return get_black(x2, y2) - get_black(x1 - 1, y2) - get_black(x2, y1 - 1) + get_black(x1 - 1, y1 - 1);
}
LL get_rec_white(LL x1, LL y1, LL x2, LL y2) {
return get_white(x2, y2) - get_white(x1 - 1, y2) - get_white(x2, y1 - 1) + get_white(x1 - 1, y1 - 1);
}
LL minx, miny, maxx, maxy;
int get_inter(LL x1, LL y1, LL x2, LL y2, LL x3, LL y3, LL x4, LL y4) {
minx = max(x1, x3);
miny = max(y1, y3);
maxx = min(x2, x4);
maxy = min(y2, y4);
if(minx > maxx || miny > maxy) return -1;
else return 1;
}
int main() {
#ifndef ONLINE_JUDGE
FIN
#endif
long long s1, s2, same;
int T;
scanf("%d", &T);
while(T--) {
scanf("%lld %lld", &n, &m);
// swap(n,m);
scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
scanf("%lld %lld %lld %lld", &x3, &y3, &x4, &y4);
wsum = get_white(n, m);
bsum = get_black(n, m);
s1 = get_rec_black(x1, y1, x2, y2);
wsum += s1;
bsum -= s1;
if(get_inter(x1, y1, x2, y2, x3, y3, x4, y4) == -1) {
s2 = get_rec_white(x3, y3, x4, y4);
bsum += s2;
wsum -= s2;
} else {
s2 = get_rec_white(x3, y3, x4, y4) - get_rec_white(minx, miny, maxx, maxy);
bsum += s2;
wsum -= s2;
bsum += (maxy - miny + 1) * (maxx - minx + 1);
wsum -= (maxy - miny + 1) * (maxx - minx + 1);
}
printf("%lld %lld\n", wsum, bsum);
}
}
codeforces 1080D
传送门：https://codeforces.com/contest/1080/problem/D
题意：你每次操作可以将一个正方形格子切割成相等的四份，形如：
当正方形边长为1时就不可以再切割了，给你一个边长为\(2^n\)的正方形，问你切k刀是否满足以下条件：
1、左下角的格子的边长等于右上角格子的边长
2、从左下角到右上角的路径上经过的格子的边长相等,即从起点到终点经过的格子相同
如果可以就打印路径长的对数长度，答案不唯一
题解：枚举正方形边长，因为答案显然小于32的
反证法：如果答案大于32，正方形边长就大于2^32=4e9，所以如果n>32时，我们输出n-1即可
如果n<32，我们开始枚举答案，答案是否合法性应该这样判断
令边长为 2^x 的正方形全部剪成 1*1 的操作数为 f(x)，有：
\[f(x)=4∗f(x−1)+1=1+4+4^2+...4^x-1=(4^x-1)/3
\]
\]
剩下的正方形的个数（不在路径上的正方形）
\[g(x)=2∗(g(x−1)−1)+5
\]
\]
于是我们就可以将剩下的正方形全部切割为边长为1的正方形
假设其花费为p
\[p=\sum(4^x-1)/3*g(x)
\]
\]
将路径上的正方形切割为长度相等的正方形的贡献是q
\[q=\sum_{i=n-1}^{1}((1<<n-i)-1)
\]
\]
倘如k-p<=q<=k，则该边长合法
参考：https://blog.csdn.net/Tiw_Air_Op1721/article/details/84454136
/**
* ┏┓ ┏┓
* ┏┛┗━━━━━━━┛┗━━━┓
* ┃ ┃
* ┃ ━ ┃
* ┃ ＞ ＜ ┃
* ┃ ┃
* ┃... ⌒ ... ┃
* ┃ ┃
* ┗━┓ ┏━┛
* ┃ ┃ Code is far away from bug with the animal protecting
* ┃ ┃ 神兽保佑,代码无bug
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┗━━━┓
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛
*/
// warm heart, wagging tail,and a smile just for you!
//
// _ooOoo_
// o8888888o
// 88" . "88
// (| -_- |)
// O\ = /O
// ____/`---'\____
// .' \| |// `.
// / \||| : |||// \
// / _||||| -:- |||||- \
// | | \\ - /// | |
// | \_| ''\---/'' | |
// \ .-\__ `-` ___/-. /
// ___`. .' /--.--\ `. . __
// ."" '< `.___\_<|>_/___.' >'"".
// | | : `- \`.;`\ _ /`;.`/ - ` : | |
// \ \ `-. \_ __\ /__ _/ .-` / /
// ======`-.____`-.___\_____/___.-`____.-'======
// `=---='
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// 佛祖保佑 永无BUG
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL;
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define bug printf("*********\n")
#define FIN freopen("input.txt","r",stdin);
#define FON freopen("output.txt","w+",stdout);
#define IO ios::sync_with_stdio(false),cin.tie(0)
#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"
#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"
#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"
const int BufferSize = 1 << 16;
char buffer[BufferSize], *head, *tail;
inline char Getchar() {
if(head == tail) {
int l = fread(buffer, 1, BufferSize, stdin);
tail = (head = buffer) + l;
}
return *head++;
}
inline int read() {
int x = 0, f = 1; char c = Getchar();
for(; !isdigit(c); c = Getchar()) if(c == '-') f = -1;
for(; isdigit(c); c = Getchar()) x = x * 10 + c - '0';
return x * f;
}
const double eps = 1e-8;
const int mod = 1e9 + 7;
const int maxn = 3e5 + 5;
const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3f;
LL quick_pow(LL x, int y) {
LL ans = 1;
while(y) {
if(y & 1) ans = ans * x ;
y >>= 1;
x = x * x;
}
return ans;
}
LL GetTotal(int b) {
return (quick_pow(4, b) - 1) / 3;
}
void solve() {
int n;
LL k;
scanf("%d%lld", &n, &k);
if( n >= 32 ) {
printf("YES %d\n", n - 1);
return ;
} else {
LL p = 0, q = 0, tmp = 1;
for(int i = n - 1; i >= 0; i--) {
q += (1LL << (n - i)) - 1;
p += 1LL * tmp * GetTotal(i);
tmp = (tmp - 1) * 2 + 5;
if( q <= k && q >= k - p ) {
printf("YES %d\n", i);
return ;
} else if( q > k ) break;
}
printf("NO\n");
}
}
int main() {
#ifndef ONLINE_JUDGE
FIN
#endif
int T;
scanf("%d", &T);
while(T--) {
solve();
}
}
codeforces 1080E
传送门：https://codeforces.com/contest/1080/problem/E
题意：给你一个n*m的字符矩阵，问你有多少个子矩阵在可以交换当前子矩阵元素位置后满足回文矩阵的性质
题解：首先我们要知道，求一个字符串的回文子串的个数可以用Manacher算法O（2*len）来求解
如果该矩阵是回文矩阵，应该满足矩阵的对称行相等的性质，即第i行与第n-i+1行是要相等的，倘若将每一行进行Hash一下的话，回文矩阵的就演变成了，对于一个长度m的字符串，求其回文子串个数。
因为题目给的n，m并不大，所以我们对于每一行，可以枚举其子矩阵的左边界和右边界，然后对于统计当前子矩阵每一行的字母的个数。如果字母个数为奇数的字母种类数小于等于两个的话，这一行经过字母重排后就可以得到回文子串了，边统计边对每一个字符进行hash，统计完所有行后对hash后的回文子矩阵 做一遍Manacher即可得到答案
复杂度约为O(n^3)
tag：Manacher
/**
* ┏┓ ┏┓
* ┏┛┗━━━━━━━┛┗━━━┓
* ┃ ┃
* ┃ ━ ┃
* ┃ ＞ ＜ ┃
* ┃ ┃
* ┃... ⌒ ... ┃
* ┃ ┃
* ┗━┓ ┏━┛
* ┃ ┃ Code is far away from bug with the animal protecting
* ┃ ┃ 神兽保佑,代码无bug
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┗━━━┓
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛
*/
// warm heart, wagging tail,and a smile just for you!
//
// _ooOoo_
// o8888888o
// 88" . "88
// (| -_- |)
// O\ = /O
// ____/`---'\____
// .' \| |// `.
// / \||| : |||// \
// / _||||| -:- |||||- \
// | | \\ - /// | |
// | \_| ''\---/'' | |
// \ .-\__ `-` ___/-. /
// ___`. .' /--.--\ `. . __
// ."" '< `.___\_<|>_/___.' >'"".
// | | : `- \`.;`\ _ /`;.`/ - ` : | |
// \ \ `-. \_ __\ /__ _/ .-` / /
// ======`-.____`-.___\_____/___.-`____.-'======
// `=---='
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// 佛祖保佑 永无BUG
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL;
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define bug printf("*********\n")
#define FIN freopen("input.txt","r",stdin);
#define FON freopen("output.txt","w+",stdout);
#define IO ios::sync_with_stdio(false),cin.tie(0)
#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"
#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"
#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3f;
const int maxn = 257;
char str[maxn][maxn];
int n, m, num[maxn], Hash[maxn], ans, mod = 19260817, base = 131;
struct Manacher {
//半径
int p[maxn << 1], str[maxn << 1];
//拿hash值来马拉车
bool check(int x) {//检查字母个数是否符合要求
return x - (x & -x) == 0;
}
bool equal(int x, int y) {//检查一行
if ((x & 1) != (y & 1)) return false;
return (x & 1) || (check(num[x >> 1]) && check(num[y >> 1]) && str[x] == str[y]);
}
int solve(int len) {
int max_right = 0, id = 0, ans = 0;
for (int i = 1; i <= len; i++) {
p[i] = (max_right > i ? min(p[id * 2 - i], max_right - i) : 1);
if ((i & 1) || check(num[i >> 1])) {
while (equal(i + p[i], i - p[i])) p[i]++;
if (max_right < i + p[i]) id = i, max_right = i + p[i];
ans += p[i] / 2;
} else p[i] = 2;
}
return ans;
}
} manacher;
//要想形成回文串，当且仅当这一行的每个字母的数量为奇数的字母小于等于两个
int main() {
#ifndef ONLINE_JUDGE
FIN
#endif
scanf("%d%d", &n, &m);
manacher.str[0] = -1, manacher.str[n * 2 + 2] = -2, Hash[0] = 1;
//Hash一下，预处理hash数组
for (int i = 1; i <= 26; i++) Hash[i] = int(1ll * Hash[i - 1] * base % mod);
for (int i = 1; i <= n; i++) scanf("%s", str[i] + 1);
for (int l = 1; l <= m; l++) {
//重置每一行的数量
for (int i = 1; i <= n; i++) num[i] = manacher.str[i << 1] = 0;
//枚举左右区间
for (int r = l; r <= m; r++) {
//对于每一列做一个Hash
for (int i = 1; i <= n; i++) {
//统计每一行字母的个数
num[i] ^= (1 << (str[i][r] - 'a'));
manacher.str[i << 1] = (manacher.str[i << 1] + Hash[str[i][r] - 'a' + 1]) % mod;
}
ans += manacher.solve(n << 1 | 1);
// debug3(l, r, ans);
// for(int j = 1; j <= n; j++) {
// debug2(j, num[j]);
// }
}
}
printf("%d\n", ans);
return 0;
}
codeforces 1080F
传送门：https://codeforces.com/contest/1080/problem/F
题意:有n个集合，m条线段，每条线段由左端点l和右端点r表示，q次询问，询问是否在集合[l,r]中都有至少 一条线段可以完全覆盖区间a,b
题解：p个集合代表线段树的p个节点，然后每次在p点插入一个线段[l，r]的时候， 在所有包含p的区间 代表的线段树 都在l的位置插入一个r， 询问 a,b,x,y的时候， 询问区间[a,b]的所有线段树中[1, x]的最大值是多少，大不大于y。 空间和时间都是nlglg(n)
wxkupup
为了不让询问时的复杂度爆炸，我们应该将查询的复杂度由nlogn降到logn级别的，我们将所有线段按照左端点从大到小排序，按顺序插入到可持久化线段树中，这样对于 每次查询我们都可以得到
\[\max_{a,b}len[i][x]
\]
\]
即在集合i中，从左端点x开始可以延申到的最大值的了
tag:可持久化线段树
/**
* ┏┓ ┏┓
* ┏┛┗━━━━━━━┛┗━━━┓
* ┃ ┃
* ┃ ━ ┃
* ┃ ＞ ＜ ┃
* ┃ ┃
* ┃... ⌒ ... ┃
* ┃ ┃
* ┗━┓ ┏━┛
* ┃ ┃ Code is far away from bug with the animal protecting
* ┃ ┃ 神兽保佑,代码无bug
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┗━━━┓
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛
*/
// warm heart, wagging tail,and a smile just for you!
//
// _ooOoo_
// o8888888o
// 88" . "88
// (| -_- |)
// O\ = /O
// ____/`---'\____
// .' \| |// `.
// / \||| : |||// \
// / _||||| -:- |||||- \
// | | \\ - /// | |
// | \_| ''\---/'' | |
// \ .-\__ `-` ___/-. /
// ___`. .' /--.--\ `. . __
// ."" '< `.___\_<|>_/___.' >'"".
// | | : `- \`.;`\ _ /`;.`/ - ` : | |
// \ \ `-. \_ __\ /__ _/ .-` / /
// ======`-.____`-.___\_____/___.-`____.-'======
// `=---='
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// 佛祖保佑 永无BUG
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL;
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define bug printf("*********\n")
#define FIN freopen("input.txt","r",stdin);
#define FON freopen("output.txt","w+",stdout);
#define IO ios::sync_with_stdio(false),cin.tie(0)
#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"
#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"
#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"
const int BufferSize = 1 << 16;
char buffer[BufferSize], *head, *tail;
inline char Getchar() {
if(head == tail) {
int l = fread(buffer, 1, BufferSize, stdin);
tail = (head = buffer) + l;
}
return *head++;
}
inline int read() {
int x = 0, f = 1; char c = Getchar();
for(; !isdigit(c); c = Getchar()) if(c == '-') f = -1;
for(; isdigit(c); c = Getchar()) x = x * 10 + c - '0';
return x * f;
}
const double eps = 1e-8;
const int mod = 1e9 + 7;
const int maxn = 3e5 + 5;
const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
struct zhuxishu {
struct node {
int l, r, val;
node(): val(INF), l(0), r(0) {}
} T[maxn * 40];
int cnt = 0, sz;
int root[maxn << 2];
void push_up(int rt) {
T[rt].val = max(T[T[rt].l].val, T[T[rt].r].val);
return;
}
void update(int pos, int val, int &rt, int pre, int l, int r) {
T[rt = ++sz] = T[pre];
if(l == r) {
T[rt].val = min(T[rt].val, val);
return;
}
int mid = (l + r) >> 1;
if(pos <= mid) update(pos, val, T[rt].l, T[pre].l, l, mid);
else update(pos, val, T[rt].r, T[pre].r, mid + 1, r);
push_up(rt);
}
int query(int L, int R, int rt, int l, int r) {
if(rt == 0) return INF;
if(L <= l && r <= R) return T[rt].val;
int mid = (l + r) >> 1;
int ans = 0;
if(L <= mid) ans = max(ans, query(L, R, T[rt].l, l, mid));
if(R > mid) ans = max(ans, query(L, R, T[rt].r, mid + 1, r));
return ans ? ans : INF;
}
void update(int pos, int val) {
++cnt;
update(pos, val, root[cnt], root[cnt - 1], 1, n);
}
int query(int l, int r, int cur) {
return query(l, r, root[cur], 1, n);
}
} H;
int key[maxn << 2], value[maxn << 2];
int len;
struct Segment {
int l, r, p;
} T[maxn << 2];
bool cmp(Segment a, Segment b) {
if(a.l == b.l) return a.r > b.r;
return a.l > b.l;
}
int main() {
#ifndef ONLINE_JUDGE
FIN
#endif
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= k; i++) {
int l, r, p;
scanf("%d%d%d", &T[i].l, &T[i].r, &T[i].p);
}
len = 0;
sort(T + 1, T + k + 1, cmp);
for(int i = 1; i <= k; i++) {
if (T[i].l != T[i - 1].l) key[++len] = T[i].l;
value[len] = i;
H.update(T[i].p, T[i].r);
}
int a, b, x, y;
while(m--) {
scanf("%d%d%d%d", &a, &b, &x, &y);
int pos = value[int(upper_bound(key + 1, key + 1 + len, x, greater<int>()) - key) - 1];
puts(H.query(a, b, pos) <= y ? "yes" : "no");
fflush(stdout);
}
return 0;
}