洛谷刷题7.30

P2346 四子连棋 - 洛谷

 依旧暴力地广搜，只不过这里的状态比较复杂，需要有耐心。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define samplepassediscorrect for(;;)
#define lowbit(x) (x&(-x))
using namespace std;
struct point{char a[6][6],flag;int step;
}; 
bool check(point s){char a[5][5];for(int i=1;i<=4;i++)for(int j=1;j<=4;j++)a[i][j]=s.a[i][j];for(int i=1;i<=4;i++){if(a[i][1]==a[i][2]&&a[i][2]==a[i][3]&&a[i][3]==a[i][4]) return true;if(a[1][i]==a[2][i]&&a[2][i]==a[3][i]&&a[3][i]==a[4][i]) return true;}if(a[1][1]==a[2][2]&&a[2][2]==a[3][3]&&a[3][3]==a[4][4]) return true;if(a[4][1]==a[3][2]&&a[3][2]==a[2][3]&&a[2][3]==a[1][4]) return true;return false;
}
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0}; 
set<string>vis;
string get(point x){string k="";for(int i=1;i<=4;i++){for(int j=1;j<=4;j++){k=k+x.a[i][j];}}return k+x.flag;
}
int main(){
point s1,s2;
memset(s1.a,' ',sizeof(s1.a));
memset(s2.a,' ',sizeof(s2.a));
string k;
for(int i=1;i<=4;i++){for(int j=1;j<=4;j++){cin>>s1.a[i][j];s2.a[i][j]=s1.a[i][j];k=k+s1.a[i][j];}
}
s1.flag='B',s2.flag='W';
vis.insert(get(s1)),vis.insert(get(s2));
s1.step=0,s2.step=0;
queue<point>r;
r.push(s1),r.push(s2);
while(!r.empty()){point temp=r.front();if(check(temp)){cout<<temp.step;return 0;}int x1=0,x2=0,y1=0,y2=0,cnt=0;for(int i=1;i<=4;i++){for(int j=1;j<=4;j++){if(temp.a[i][j]=='O'){if(!cnt) x1=i,y1=j,cnt++;else x2=i,y2=j,cnt++;;}if(cnt==2) break;}if(cnt==2) break;}for(int i=0;i<4;i++){temp=r.front();if(temp.a[x1+dx[i]][y1+dy[i]]==temp.flag){swap(temp.a[x1][y1],temp.a[x1+dx[i]][y1+dy[i]]);temp.flag=(temp.flag=='B')?'W':'B';temp.step++;if(vis.find(get(temp))==vis.end()){vis.insert(get(temp));r.push(temp);}				}temp=r.front();if(temp.a[x2+dx[i]][y2+dy[i]]==temp.flag){swap(temp.a[x2][y2],temp.a[x2+dx[i]][y2+dy[i]]);temp.flag=(temp.flag=='B')?'W':'B';temp.step++;if(vis.find(get(temp))==vis.end()){vis.insert(get(temp));r.push(temp);}	}}r.pop();
}return 0;
}

 P1637 三元上升子序列 - 洛谷

 很明显，我们枚举中间值，在它前面找小于它的个数，在它后面找大于它的个数，相乘后累加就是答案。这里是不是很像逆序数，不过这里应该是顺序数。因为是严格的大于，所以相同的数要离散化为同一值。用两个树状数组就能轻松搞定。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define samplepassediscorrect for(;;)
#define lowbit(x) (x&(-x))
#define MAXN 50005
using namespace std;
ll n,a[MAXN],b[MAXN],ans1[MAXN],ans2[MAXN];
struct Fenwick_Tree{ll tree[MAXN];void add(int x,int num){while(x<=n){	    tree[x]+=num;x+=lowbit(x);}}ll search(int x){	ll re=0;while(x){   re+=tree[x];x-=lowbit(x);}return re;}
}r1,r2;
struct point{ll x,num;
}temp[MAXN];
bool cmp(point &s1,point &s2){return s1.x<s2.x;};
int main(){
jiasu;
cin>>n;
for(int i=1;i<=n;i++){cin>>a[i];temp[i].x=a[i];temp[i].num=i;
}
sort(temp+1,temp+1+n,cmp);
ll now=0,cnt=0;
for(int i=1;i<=n;i++){if(now!=temp[i].x){b[temp[i].num]=++cnt;now=temp[i].x;}else b[temp[i].num]=cnt;
}
for(int i=1;i<=n;i++){ans1[i]=r1.search(b[i]-1);r1.add(b[i],1);
}
for(int i=n;i>=1;i--){ans2[i]=r2.search(n)-r2.search(b[i]);r2.add(b[i],1);
}
ll sum=0;
for(int i=1;i<=n;i++) sum+=ans1[i]*ans2[i];
cout<<sum;return 0;
}

P4868 Preprefix sum - 洛谷

依旧是线段树模板题，不需要任何改造。把a[i]改为k，就是将sum[i]——sum[n]都加上k-a[i]         前前缀和就是查询前缀和的1——x的区间和，我们用线段树来维护一次前缀和，这就用到了线段树的区间修改，区间查询的功能。 注意，修改之后a[i]要改为k

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define samplepassediscorrect for(;;)
#define lowbit(x) (x&(-x))
#define N 500005
using namespace std;
ll n,a[N],m,input[N];
struct node{long long r,l,sum,lz;
};
struct Segment_Tree{node tree[N];void push_down(int i){//下传函数	if(tree[i].lz!=0){		tree[i*2].lz+=tree[i].lz;tree[i*2+1].lz+=tree[i].lz;tree[i*2].sum+=tree[i].lz*(tree[i*2].r-tree[i*2].l+1);tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-tree[i*2+1].l+1);tree[i].lz=0;}return;}void build(int i,int l,int r){//建树tree[i].l=l,tree[i].r=r;tree[i].lz=0;if(l==r){	tree[i].sum=input[l];return;}int mid=(l+r)/2;build(2*i,l,mid);build(2*i+1,mid+1,r);tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;}void add(int i,int l,int r,int k){//区间加减if(tree[i].l>=l&&tree[i].r<=r){	tree[i].sum+=k*(tree[i].r-tree[i].l+1);tree[i].lz+=k;return;}push_down(i);if(tree[i*2].r>=l) add(i*2,l,r,k);if(tree[i*2+1].l<=r) add(i*2+1,l,r,k);tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;return;}ll search(int i,int l,int r){//查询if(tree[i].l>=l&&tree[i].r<=r) return tree[i].sum;if(tree[i].r<l||tree[i].l>r) return 0;push_down(i);long long ans=0;if(tree[i*2].r>=l) ans+=search(i*2,l,r);if(tree[i*2+1].l<=r) ans+=search(i*2+1,l,r);return ans;}
}r;
int main(){
jiasu;
cin>>n>>m;
ll sum=0;
for(int i=1;i<=n;i++){cin>>a[i];input[i]=input[i-1]+a[i];
}
r.build(1,1,n);
string s;
ll x,y;
while(m--){cin>>s;if(s=="Query"){cin>>x;cout<<r.search(1,1,x)<<endl;}else{cin>>x>>y; r.add(1,x,n,y-a[x]);a[x]=y;}
}return 0;
}

 P5057 [CQOI2006] 简单题 - 洛谷

题如其名，真的是简单题。我们只需维护每个点的操作次数，如果是奇数就是1，如果是偶数就是0。这用到线段树的区间修改，单点查询。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define samplepassediscorrect for(;;)
#define lowbit(x) (x&(-x))
#define N 500005
using namespace std;
ll n,a[N],m,input[N];
struct node{long long r,l,sum,lz;
};
struct Segment_Tree{node tree[N];void push_down(int i){//下传函数	if(tree[i].lz!=0){		tree[i*2].lz+=tree[i].lz;tree[i*2+1].lz+=tree[i].lz;tree[i*2].sum+=tree[i].lz*(tree[i*2].r-tree[i*2].l+1);tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-tree[i*2+1].l+1);tree[i].lz=0;}return;}void build(int i,int l,int r){//建树tree[i].l=l,tree[i].r=r;tree[i].lz=0;if(l==r){	//		tree[i].sum=input[l];return;}int mid=(l+r)/2;build(2*i,l,mid);build(2*i+1,mid+1,r);tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;}void add(int i,int l,int r,int k){//区间加减if(tree[i].l>=l&&tree[i].r<=r){	tree[i].sum+=k*(tree[i].r-tree[i].l+1);tree[i].lz+=k;return;}push_down(i);if(tree[i*2].r>=l) add(i*2,l,r,k);if(tree[i*2+1].l<=r) add(i*2+1,l,r,k);tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;return;}ll search(int i,int l,int r){//查询if(tree[i].l>=l&&tree[i].r<=r) return tree[i].sum;if(tree[i].r<l||tree[i].l>r) return 0;push_down(i);long long ans=0;if(tree[i*2].r>=l) ans+=search(i*2,l,r);if(tree[i*2+1].l<=r) ans+=search(i*2+1,l,r);return ans;}
}r;
int main(){
jiasu;
cin>>n>>m;
r.build(1,1,n);
ll flag,x,y;
while(m--){cin>>flag;if(flag==1){cin>>x>>y;r.add(1,x,y,1);}else{cin>>x;ll ans=r.search(1,x,x);cout<<ans%2<<endl;}
}return 0;
}

 P9588 「MXOI Round 2」队列 - 洛谷

单调队列模拟题，我们会发现插入的数的个数就是1操作的x，那么我们累加x得到前缀和就是目前序列的长度，删去y个就是查找前缀和>=y+z的点，如果前缀和<y+z，那么肯定已经被删完了。我们得到的刚好大于等于y+z的那个点的下标，看sum[i]大于y多少，再用a[i]减去多余的数就是第z个数。 对应操作4也是现将小于等于y的点出优先队列，再查询最大值。

#include<bits/stdc++.h>
#define ll long long
#define samplepassediscorrect for(;;)
#define ull unsigned long long
#define jiasu ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define N 200005
using namespace std;
ll t,c,a[N],n,f,x,sum[N],y;
deque<ll>q;
void put(ll x){while(!q.empty()&&a[q.back()]<=a[x]){q.pop_back();}q.push_back(x);
}
void out(ll x){while(!q.empty()&&q.front()<x){q.pop_front();}
}
int main()
{
jiasu;
cin>>c>>t;
while(t--){cin>>f;if(f==1){cin>>x;a[++n]=x;sum[n]=sum[n-1]+x;put(n);}else if(f==2){cin>>x;y+=x;}else if(f==3){cin>>x;ll i=lower_bound(sum+1,sum+1+n,y+x)-sum;cout<<a[i]-sum[i]+y+x<<endl;}else{ll k=upper_bound(sum+1,sum+1+n,y)-sum;out(k);cout<<a[q.front()]<<endl;}
}return 0;
}