SMZX十日游（第二阶段模拟赛）
创作背景
“老师，学这么多内容，是不是准备要模拟赛了”
“恭喜你，猜对了”
题目清单
- 朋友？敌人？（enemy.cpp）
- 区间微调（adjust.cpp）
- 奇异区间（pair.cpp）
详细讲解 如何被虐
朋友？敌人？
题目描述
有n个人，在他们之中有些人互相是朋友，有些人则是另一些人的敌人，一开始你并不知道他们的关系。要注意的是，这里遵循敌人的敌人是朋友的原则，且自己也可算作自己的朋友。
接下来有m个操作，操作有3种：
1x y：告诉你x和y是朋友。如果该信息与之前的有矛盾，则输出“Conflict”，否则输出”Ok”。
2x y：告诉你x和y是敌人。如果该信息与之前的有矛盾，则输出“Conflict”，否则输出”Ok”。
3 x y：询问x和y的关系，如果是朋友输出“Friend”（不带引号，下同），是敌人输出”Enemy”，不知道输出”Unknown”。
输入格式
第一行两个整数n，m。
接下来m行，每行三个整数，代表一个操作，具体格式见问题描述。
输出格式
对于每个询问输出一行一个单词，表示询问的结果。
样例输入输出
样例输入1
5 7
3 1 2
1 1 2
1 1 3
3 2 3
2 2 4
3 1 4
1 1 4
样例输出1
Unknown
Ok
Ok
Friend
Ok
Enemy
Conflict
样例输入输出2
见超链接（如需要积分，可以博主联系）
思路
这不就只一个简简单单的并查集吗？然而我却没有写出来（还是太弱了）
赛后根据老师的讲评，发现实际上不是很难
首先，举个例子，现在的形势图如下：
现在问你：1 和 5什么关系？
解决这个问题，你要先知道：敌人的敌人是自己的盆友
所以2个敌人可以直接归并为朋友
以此类推，只要是偶数个敌人，都能成为朋友
再加上路径压缩（忘记的戳这里回顾一下）
一个并查集就出现了：
Code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int n, m, fa[maxn], dis[maxn];
int F(int x)
{
if (x == fa[x])
return x;
int father = fa[x];
fa[x] = F(fa[x]);
dis[x] ^= dis[father];//就是取反，说白了就是看看到底敌人的关系链是不是偶数，一直在敌人和朋友两个角色左右横跳
return fa[x];
}
int main()
{
freopen("enemy.in", "r", stdin);
freopen("enemy.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
fa[i] = i, dis[i] = 0;//初始化
for (int i = 0; i < m; i++) {
int op, x, y;
scanf("%d%d%d", &op, &x, &y);
if (op <= 2) {
// 就是建立关系网
int rx = F(x), ry = F(y);
if (rx == ry) {
if ((dis[x] ^ dis[y]) == (op - 1))
printf("Ok\n");
else
printf("Conflict\n");
continue;
}
fa[rx] = ry;
dis[rx] = (op - 1) ^ dis[x] ^ dis[y];
printf("Ok\n");
} else {
// query
int rx = F(x), ry = F(y);
if (rx != ry) {
printf("Unknown\n");
continue;
}
if ((dis[x] ^ dis[y]) == 0)
printf("Friend\n");
else
printf("Enemy\n");
}
}
return 0;
}
区间微调
题目描述
小H手头上有一个n个数的序列，但他觉得这个序列不够完美，决定进行一些微调。现在他需要你完成m个操作，操作有两种：
1 l r：对于区间[l,r]中的数，第1个数+1，第2个数-1，第3个数+1，第4个数-1，如此类推。
2 l r：询问区间[l,r]的和。
输入格式
第一行两个整数n,m。
第二行n个整数，代表序列中的n个数。
接下来m行，每行三个整数，代表上述的某个操作。
输出格式
对于每个询问输出一行一个整数，代表该询问的结果。
输入输出样例
样例输入1
5 4
1 2 3 4 5
1 1 3
2 2 4
1 2 4
2 3 5
样例输出1
9
13
样例输入输出2
见超链接（如需要积分，可以博主联系）
数据范围
50%: 1 <= n <= 3000.
100%: 1 <= n <= 100000 , 1 <= ai <10 ^ 9.
思路
看看这题，改变数据，求区间和，那不就是：
(戳这里回顾一下)
首先，这里是要改变区间的值，这个十分简单，但是：
这个先+1后-1就很恶心了
怎么办呢？本人一开始的想法是：
既然有了for语句，干脆连区间修改都不用了，直接单点修改。真的不是因为不会打lazy标记
所以一份TLE的代码就完成了
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100005;
long long n,m,tree[4*maxn],tag[4*maxn],a[maxn];
inline void build (int rt, int l,int r)//建树
{
if(l == r)
{
tree[rt]=a[l];
return ;
}
int mid=(l+r)>>1;
build(rt+rt , l , mid);
build(rt+rt+1 , mid+1 , r);
tree[rt]= tree[rt+rt] + tree[rt+rt+1];
}
inline void update(int rt, int l, int r, int x, int val)//单点修改
{
if (x > r || x < l) return ;
if (x == l && x == r)
{
tree[rt] += val;
return ;
}
int mid=(l+r)>>1;
update(rt+rt, l, mid, x, val);
update(rt+rt+1, mid+1, r, x, val);
tree[rt] = tree[rt + rt] + tree[rt + rt + 1];
}
inline long long ask(int rt,int l,int r,int ll,int rr)//查询区间和
{
if (ll > r || rr < l) return 0;
if (ll <= l && rr >= r) return tree[rt];
int mid=(l+r) >> 1;
return ask(rt+rt, l, mid, ll, rr)+ask(rt+rt+1, mid+1, r, ll, rr);
}
int main()
{
freopen("adjust.in","r",stdin);
freopen("adjust.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
for(int i=1;i<=m;i++)
{
int l,r,c;
cin>>c>>l>>r;
if(c==1)
{
for(int j=1;j<=r-l+1;j++)
{
if (j % 2 == 1)
update(1,1,n,l+j-1,1);
else
update(1,1,n,l+j-1,-1);
}
}
else cout<<ask(1,1,n,l,r)<<endl;
}
}
但是，好好看看这个数据范围：1e6，双for就是1e12,100%TLE
so正解到底是什么？
观察一下，+1，-1，+1……所以说只要区间为偶数，那么他的区间和就不会变，如果为奇数，只需要看看+1还是-1即可
Code
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
const int maxn = 100005;
int n, m, a[maxn];
long long tree[4 * maxn], tag[4 * maxn];
void build(int rt, int l, int r)
{
tag[rt] = 0;
if (l == r) {
tree[rt] = a[l];
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
tree[rt] = tree[lson] + tree[rson];
}
inline void down(int rt, int l, int mid, int r)
{
int t = tag[rt];
if (t == 0)
return;
tag[rt] = 0;
tree[lson] += (mid - l + 1) % 2 * t;//赋予+-标记
tag[lson] += t;
t *= (mid - l + 1) % 2 ? -1 : 1;
tree[rson] += (r - mid) % 2 * t;
tag[rson] += t;
}
void update(int rt, int l, int r, int x, int y)
{
if (x > r || y < l)
return;
if (x <= l && r <= y) {
int val = (l - x) % 2 ? -1 : 1; //确定要不要加减
tree[rt] += (r - l + 1) % 2 * val;//更改根点
tag[rt] += val;
return;
}
int mid = (l + r) >> 1;
down(rt, l, mid, r);
update(lson, l, mid, x, y);
update(rson, mid + 1, r, x, y);
tree[rt] = tree[lson] + tree[rson];
}
long long query(int rt, int l, int r, int x, int y)
{
if (x > r || y < l)
return 0;
if (x <= l && r <= y)
return tree[rt];
int mid = (l + r) >> 1;
down(rt, l, mid, r);
return query(lson, l, mid, x, y) + query(rson, mid + 1, r, x, y);
}
int main()
{
freopen("adjust.in", "r", stdin);
freopen("adjust.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
build(1, 1, n);
for (int i = 1; i <= m; i++) {
int op, l, r;
scanf("%d%d%d", &op, &l, &r);
if (op == 1) {
update(1, 1, n, l, r);
} else {
printf("%I64d\n", query(1, 1, n, l, r));
}
}
return 0;
}
奇异区间
题目描述
在长度为n的序列中，如果在一个区间[l,r]中存在一个数能整除该区间内的所有数，那么区间[l,r]就是一个奇异区间。请你求出奇异区间的最大长度。
输入格式
第一行一个整数n。
第二行n个整数，代表序列中的n个数。
输出格式
一行一个整数，代表奇异区间的最大长度。
样例输入输出
样例输入1
5
4 6 9 3 6
样例输出1
4
样例输入2
5
2 3 5 7 11
样例输出2
1
数据范围
30%: 1 <= n <= 30 , 1 <= ai <= 32.
60%: 1 <= n <= 3000 , 1 <= ai <= 1024.
80%: 1 <= n <= 300000 , 1 <= ai <= 1048576.
100%: 1 <= n <= 500000 , 1 <= ai < 2 ^ 31.
提示
关键词：二分答案，区间最小值，区间gcd
思路
这道题尽管有了提示，但本人过于蒟蒻，还是做不出来，但是，这题的范围看看，才30，所以：
暴力思路：
首先，枚举一个长度，在枚举一个端点，然后判断一下能不能整除，然后这不就了吗？
但是，这个操作只有最多90分，所以下面就讲一下正解。
看看关键词：二分答案，区间最小值，区间gcd。现在先一个一个解释。
gcd：看起来是不是很高级，实际上就是“最大公因数”。那这里怎么求？当然是短除法 辗转相除法。食用 使用方法如下：
int gcd(int x,int y)
{
if(y==0)
return x;
return gcd(y,x%y);
}
区间最小值：顾名思义，不解释
二分答案：不会的去恶补一下，否则这道题做起来很勉强。
那这些有什么用呢？
首先，让你用碾转相除法求2个数的最小公因数怎么求？如下图：
可以分成两部分，合并来求两部分的最大公因数.，并且怎么分都可以。而这里正好需要最大公因数，gcd不就派上用场了吗：
问你一个问题：如果一个数能整除该区间内的所有数，那么请问它在区间里面的大小情况？当然是最小值了。区间最小值不就派上用场了吗？
所以区间最小值就是最大公因数！
那么请问，如何求区间最小值，当然是ST表了，那最大公因数呢？看看，刚刚说了多个最大公因数就分成两部分，无限分成两部分，最后分成两个，等等，这不就一个单纯的ST表吗？所以本题的核心：
等等，二分答案又有什么用？你忘记了还要最后搜索区间最小值等不等于最大公因数吗？，这不就用上了了吗？
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define ll long long
#define inf 2147483647
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int bin[20];
int n,top,res;
int a[500005],L[500005],q[500005],ans[500005];
int mn[500005][19],g[500005][19];
int gcd(int x,int y)
{
return y==0?x:gcd(y,x%y);
}
void pre()
{
for(int i=1;i<=n;i++)
mn[i][0]=g[i][0]=a[i];
for(int j=1;j<=18;j++)
for(int i=1;i<=n;i++)
{
if(i+bin[j]-1<=n)
{
mn[i][j]=min(mn[i][j-1],mn[i+bin[j-1]][j-1]);//mn是求最小值
g[i][j]=gcd(g[i][j-1],g[i+bin[j-1]][j-1]);//g就是公因数
}
else break;
}
}
bool query(int l,int r)
{
int t=L[r-l+1],R=r-bin[t]+1;
return min(mn[l][t],mn[R][t])==gcd(g[l][t],g[R][t]);//判断相不相等
}
void solve(int x)
{
for(int i=1;i<=n;i++)
if(i+x-1<=n)
if(query(i,i+x-1))
ans[++top]=i;
}
int main()
{
freopen("pair.in","r",stdin);
freopen("pair.out","w",stdout);
bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;
L[0]=-1;for(int i=1;i<=500000;i++)L[i]=L[i>>1]+1;
n=read();
for(int i=1;i<=n;i++)a[i]=read();
pre();
int l=1,r=500000;
while(l<=r)//二分答案
{
int mid=(l+r)>>1;
top=0;
solve(mid);
if(top)res=mid,l=mid+1;
else r=mid-1;
}
printf("%d\n",res);
return 0;
}
The End
其实呢，这次的模拟赛十分简单 就怪了，难的一匹溜了溜了，去预习图了
上一篇： Elixir中的String、binaries和bitstring
下一篇： 无重复字符的最长子串
推荐阅读