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個 ...
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的結果。
【輸入樣例】
4 1 2 3 4 2 1 2 1 2
【輸出樣例】
1 0
【數據規模】
對於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=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } int n,q,a[100100],f[100100],temp; void add(int x,int y) { for(;x<=n;x+=(x&-x)) f[x]+=y; } int ask(int x) { int ans=0; 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=1;i<=n;i++) a[i]=read(); q=read(); for(int i=n;i>=1;i--) { temp+=ask(a[i]-1); add(a[i],1); } temp&=1; for(int i=1;i<=q;i++) { int x=read(),y=read(); if(x!=y) temp^=1; cout<<temp<<endl; } return 0; }View Code
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，表示一個詢問。
【輸出格式】
對於每個詢問輸出一行表示答案。
【輸入樣例】
7 3 13 7 2 9 5 6 8 1 3 4 2 3 1
【輸出樣例】
0 18 27
【數據規模】
對於80%的數據，n≤1023，m≤1000。
對於100%的數據，n≤131071，m≤100000，n=2t-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=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } const int N=131073; 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>>1; if(y>=1&&y!=from) dfs(y,d+1,x); y=x<<1; if(y<=n&&y!=from) dfs(y,d+1,x); if(y+1<=n&&y+1!=from) dfs(y+1,d+1,x); } int main() { //freopen("dream.in","r",stdin); //freopen("dream.out","w",stdout); n=read(),m=read(); a[1]=read(); for(int i=2;i<=n;i++) a[i]=read(); for(int i=1;i<=m;i++) { int x=read(); dd=read(),ans=0; dfs(x,0,0); cout<<ans<<endl; } return 0; }View Code
T3 宣傳欄
題目
【題目描述】
有一個大型的矩形宣傳欄，高和寬分別為h和m。宣傳欄是用來張貼告示的地方，最初，宣傳欄是空的，但此後告示將一張一張的被放上去。
有n張告示，每張告示的高都是一個單位長度，第i張貼上的告示寬度為w[i]。
每次張貼時，總是將告示貼在可以張貼且最高的地方，如果有多個可行的地方，則選擇最左邊張貼。
給定宣傳欄的高和寬，你的任務是找出每個告示張貼在第幾行。
【輸入格式】
第一行為三個整數，h，m和n(1≤m≤109;1≤h≤n≤200000)，表示宣傳欄的尺寸和張貼的告示個數。
接下來n行表示w[i]（1≤w[i]≤109）。
【輸出格式】
每行一個整數表示答案。如果第i個告示沒地方貼，輸出-1。
【輸入樣例】
3 5 5 2 4 3 3 3
【輸出樣例】
1 2 1 3 -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=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } int h,m,n,c[800100]; int w; void build(int p,int l,int r) { c[p]=m; if(l==r) return ; int mid=(l+r)>>1; build(p*2,l,mid),build(p*2+1,mid+1,r); } int ask(int p,int l,int r) { if(l==r) { c[p]-=w; return l; } int mid=(l+r)>>1; if(c[p*2]>=w) { int temp=ask(p*2,l,mid); c[p]=max(c[p*2+1],c[p*2]); return temp; } else { int temp=ask(p*2+1,mid+1,r); c[p]=max(c[p*2+1],c[p*2]); return temp; } } int main() { //freopen("billboard.in","r",stdin); //freopen("billboard.out","w",stdout); h=read(),m=read(),n=read(); build(1,1,h); for(int i=1;i<=n;i++) { w=read(); if(w>c[1]) { cout<<"-1"<<endl; continue; } cout<<ask(1,1,h)<<endl; } return 0; }View Code
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)
{
……
}
【輸出格式】
對於每個詢問輸出一行表示答案。
【輸入樣例】
1 5 8 3 3 6 2000 2000 2000 999 999 999 233 233 233 100 100 100 40 30 20
【輸出樣例】
0 1 666 333 77 33 5
【數據規模】
對於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==0) 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<0) t+=g; return min(t,g-t); } int main() { while(cin>>a>>b>>c) { ans=0; for(y=0;y<b;y++) for(z=0;z<c;z++) { int temp; temp=min(solve(a,b,0,y),min(solve(b,c,y,z),solve(a,c,0,z))); ans=max(ans,temp); } cout<<ans<<endl; } return 0; }View Code
