T1 动态逆序对
题目
【题目描述】
给出一个长度为n的排列a（1~n这n个数在数列中各出现1次）。每次交换两个数，求逆序对数%2的结果。
逆序对：对于两个数a[i],a[j](i<j)，若a[i]>a[j]，则(a[i],a[j])为1个逆序对。
【输入格式】
第一行一个正整数n。
接下来一行n个数，表示给出的排列a。
接下来一行一个正整数q。
接下来q行，每行两个正整数i,j，表示交换a[i]和a[j]。
【输出格式】
输出共q行，表示每次交换后的逆序对数%2的结果。
【输入样例】
【输出样例】
【数据规模】
对于60%的数据：n,q≤100；
对于80%的数据：n,q≤1000；
对于100%的数据：n,q≤100000。
解析
先求出初始序列的逆序对总数对2取余的结果。
每次交换a[i]与a[j](i<j)，对于a[k]的影响如下：
- 若k<i，a[k]依旧在a[i]与a[j]前面，所以a[k]与a[i]、a[j]产生的逆序对数不变；
- 若k>j，同上，逆序对数不变；
- 若i<k<j，如果a[i]<a[k]，则逆序对数+1，否则-1,；如果a[j]>a[k]，则逆序对数+1，否则-1，
而我们只需求出逆序对数对2取余的结果，可以发现，逆序对个数的奇偶性与k无关。
事实上，只需在每次交换位置时，令逆序对总数对2取余的结果^1即可（i=j时则不变）。
Code
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
inline int read()
{
int num=,w=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-') w=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
num=(num<<)+(num<<)+ch-'';
ch=getchar();
}
return num*w;
}
int n,q,a[],f[],temp;
void add(int x,int y)
{
for(;x<=n;x+=(x&-x)) f[x]+=y;
}
int ask(int x)
{
int ans=;
for(;x;x-=(x&-x)) ans+=f[x];
return ans;
}
int main()
{
//freopen("lyk.in","r",stdin);
//freopen("lyk.out","w",stdout);
n=read();
for(int i=;i<=n;i++) a[i]=read();
q=read();
for(int i=n;i>=;i--)
{
temp+=ask(a[i]-);
add(a[i],);
}
temp&=;
for(int i=;i<=q;i++)
{
int x=read(),y=read();
if(x!=y) temp^=;
cout<<temp<<endl;
}
return ;
}
T2 树的统计
题目
【题目描述】
给出一棵n个点的满二叉树，根节点为1，第i个点的左右子节点分别为第2i,2i+1个点，第i个点的权值为a[i]。
有m个询问。对于每个询问给出x,d，求到点x的距离为d的所有点的点权和。如果不存在符合条件的点，输出0。
两点距离即两点间最短路径的边数。
保证最终答案在int范围内。
【输入格式】
第一行两个正整数n,m。
接下来n行每行一个正整数，第i行的数表示a[i]。
接下来m行每行两个整数x,d，表示一个询问。
【输出格式】
对于每个询问输出一行表示答案。
【输入样例】
【输出样例】
【数据规模】
对于80%的数据，n≤1023，m≤1000。
对于100%的数据，n≤131071，m≤100000，n=2-1，1≤t≤17，a[i]≤30000。
解析
对于每个询问，用dfs搜索与点x距离为d的点，进行统计即可。
注意每个点之间的关系，访问父亲是x<<1，左儿子是x>>1，右儿子是x>>1+1，要特判一下左右儿子编号不能大于n，否则会RE。
Code
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
inline int read()
{
int num=,w=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-') w=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
num=(num<<)+(num<<)+ch-'';
ch=getchar();
}
return num*w;
}
const int N=;
int n,m,a[N],dd,ans;
void dfs(int x,int d,int from)
{
if(d>dd) return ;
if(d==dd)
{
ans+=a[x];
return ;
}
int y=x>>;
if(y>=&&y!=from) dfs(y,d+,x);
y=x<<;
if(y<=n&&y!=from) dfs(y,d+,x);
if(y+<=n&&y+!=from) dfs(y+,d+,x);
}
int main()
{
//freopen("dream.in","r",stdin);
//freopen("dream.out","w",stdout);
n=read(),m=read();
a[]=read();
for(int i=;i<=n;i++) a[i]=read();
for(int i=;i<=m;i++)
{
int x=read();
dd=read(),ans=;
dfs(x,,);
cout<<ans<<endl;
}
return ;
}
T3 宣传栏
题目
【题目描述】
有一个大型的矩形宣传栏，高和宽分别为h和m。宣传栏是用来张贴告示的地方，最初，宣传栏是空的，但此后告示将一张一张的被放上去。
有n张告示，每张告示的高都是一个单位长度，第i张贴上的告示宽度为w[i]。
每次张贴时，总是将告示贴在可以张贴且最高的地方，如果有多个可行的地方，则选择最左边张贴。
给定宣传栏的高和宽，你的任务是找出每个告示张贴在第几行。
【输入格式】
第一行为三个整数，h，m和n(1≤m≤10;1≤h≤n≤200000)，表示宣传栏的尺寸和张贴的告示个数。
接下来n行表示w[i]（1≤w[i]≤10）。
【输出格式】
每行一个整数表示答案。如果第i个告示没地方贴，输出-1。
【输入样例】
【输出样例】
-
【数据规模】
对于20%的数据，n=1。
对于40%的数据，n,m≤500。
对于70%的数据，n≤2000。
对于90%的数据，n≤50000。
对于100%的数据，n≤200000。
解析
用c[i]表示第i行还剩多少长度。
用线段树维护c[i]的区间最大值即可。
Code
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
inline int read()
{
int num=,w=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-') w=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
num=(num<<)+(num<<)+ch-'';
ch=getchar();
}
return num*w;
}
int h,m,n,c[];
int w;
void build(int p,int l,int r)
{
c[p]=m;
if(l==r) return ;
int mid=(l+r)>>;
build(p*,l,mid),build(p*+,mid+,r);
}
int ask(int p,int l,int r)
{
if(l==r)
{
c[p]-=w;
return l;
}
int mid=(l+r)>>;
if(c[p*]>=w)
{
int temp=ask(p*,l,mid);
c[p]=max(c[p*+],c[p*]);
return temp;
}
else
{
int temp=ask(p*+,mid+,r);
c[p]=max(c[p*+],c[p*]);
return temp;
}
}
int main()
{
//freopen("billboard.in","r",stdin);
//freopen("billboard.out","w",stdout);
h=read(),m=read(),n=read();
build(,,h);
for(int i=;i<=n;i++)
{
w=read();
if(w>c[])
{
cout<<"-1"<<endl;
continue;
}
cout<<ask(,,h)<<endl;
}
return ;
}
T4 种树
题目
【题目描述】
你要在一条无穷长的马路上种树。
你想种3种树，分别是草莓树，西瓜树，土豆树。
给定3个正整数A,B,C，你可以选择3个整数x,y,z，然后：
- 在位置 … , x-2A , x-A , x , x+A , x+2A , … 分别种1棵草莓树。
- 在位置 … , y-2B , y-B , y , y+B , y+2B , … 分别种1棵西瓜树。
- 在位置 … , z-2C ,z-C , z , z+C , z+2C , … 分别种1棵土豆树。
你想要最大化最近的两棵树的距离，请你输出这个最大距离。
【输入格式】
每个测试点多组测试数据。
每组数据输入一行A,B,C。
没给出数据组数，你可以这样输入：
while (scanf(“%d%d%d”, &A, &B, &C) == 3)
{
……
}
【输出格式】
对于每个询问输出一行表示答案。
【输入样例】
【输出样例】
【数据规模】
对于100%的数据，1≤A,B,C≤2000。
解析
先用solve函数求出三树两两之间最小距离的最小值，然后再找到最大的即可。
证明过程比较麻烦，本蒟蒻数论不太好，就不给出详细证明了。
Code
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
int a,b,c,x,y,z,ans;
int gcd(int x,int y)
{
if(y==) return x;
return gcd(y,x%y);
}
int solve(int a,int b,int x,int y)
{
int g=gcd(a,b);
int t=(x-y)%g;
if(t<) t+=g;
return min(t,g-t);
}
int main()
{
while(cin>>a>>b>>c)
{
ans=;
for(y=;y<b;y++)
for(z=;z<c;z++)
{
int temp;
temp=min(solve(a,b,,y),min(solve(b,c,y,z),solve(a,c,,z)));
ans=max(ans,temp);
}
cout<<ans<<endl;
}
return ;
}