首页 > 其他分享 >iwtgm-33

iwtgm-33

时间：2023-12-05 18:22:58浏览次数：36  
标签：ch val 33 void iwtgm mid int --

Codeforces Round 912 (Div. 2)

A.

只要k大等于2，那么每个数的位置就可以任意放置（两两交换可以到达任何位置），一定可以符合条件
特判序列本来就升序，那么k的值无关紧要

int n,k;
int a[110];
void solve() {
    cin>>n>>k;
    bool flag=true;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i>1){
            if(a[i]>=a[i-1])continue;
            flag=false;
        }
    }
    if(flag==true){
        cout<<"YES"<<endl;return ;
    }
    if(k>=2){
        cout<<"YES"<<endl;return ;
    }
    cout<<"NO"<<endl;
}

B.

既然这么多或，那么我们考虑与
核心思想就是满足所有条件即可
我们可以把每个数初始为每个位全1，遍历所有限制，与上它们
最后再判是否满足条件

int n;
void solve() {
    cin>>n;
    int m[n][n],arr[n];
    for(int i=0;i<n;i++)arr[i]=(1<<30)-1;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>m[i][j];
            if(i!=j){
                arr[i]&=m[i][j];
                arr[j]&=m[i][j];
            }
        }
    }
    bool ok=true;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i!=j&&((arr[i]|arr[j])!=m[i][j]))ok=false;
        }
    }
    if(!ok){
        cout<<"NO"<<endl;
    }else{
        cout<<"YES"<<endl;
        for(int i=0;i<n;i++)cout<<arr[i]<<' ';
        cout<<endl;
    }
}

C.

如果每个段都是正数，那自然是段分得越多越好，这样权值会更大
从后往前遍历，若该后缀是正数，则加权（新成一个段）
特判遍历到1

ll a[N];
void solve() {
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    ll ans=0,tmp=0;
    for(int i=n;i>=1;i--){
        tmp+=a[i];
        if(tmp>0||i==1){
            ans+=tmp;
        }
    }
    cout<<ans<<endl;
}

D1.

从最高位往低位判，若k满足把所有数的这一位都变成1的代价，就把这一位变成1（同时把这一位之后的都置为0）

#define int long long
void solve() {
    int n,q;cin>>n>>q;
    vector<int>a(n);
    for(auto &i:a)cin>>i;
    while(q--){
        int k;cin>>k;
        vector<int>b=a;
        int ans=0;
        for(int i=60;i>=0;i--){
            __int128 sum=0;
            for(auto j:b){
                int res=(j>>i)&1;
                if(res==0){
                    sum+=(1ll<<i)-(j&((1ll<<i)-1));
                }
            }
            if(sum<=k){
                k-=sum;
                ans+=(1ll<<i);
                for(auto &j:b){
                    if(!((j>>i)&1))j=(1ll<<i);
                }
            }
        }
        cout<<ans<<endl;
    }
}

D2.

无法全部理解，放一些学到的知识
sosdp

const int N=1<<22;
int f[N<<1],a[1000005],mx=(1<<22);
void solve() {
    for(int i=0;i<(1<<N);i++)f[i]=a[i];
    for(int i=0;i<N;i++){
        for(int mask=0;mask<(1<<N);mask++){
            if(mask&(1<<i))f[mask]+=f[mask^(1<<i)];//子集
            //if(!(mask&(1<<i)))f[mask]+=f[mask^(1<<i)];//超集
        }
    }
}

E.

平方不改变奇偶性，具体数不重要
x1-x2+x2-x3
可见中间数是无用的，只考虑首尾点即可
去看起点到每一个点（看成终点）的路程的奇偶性
谁多就选谁，走别人的路
小技巧，奇偶set里面记录的是位置就不用考虑重复点的情况

struct bi{
    int a,b;
};
void solve() {
    int n;cin>>n;
    vector<bi>arr(n+1);
    for(int i=0;i<=n;i++)cin>>arr[i].a>>arr[i].b;
    int c1=0,c2=0;
    multiset<int>cnt1,cnt2;
    for(int i=1;i<=n;i++){
        if((abs(arr[0].a-arr[i].a)+abs(arr[0].b-arr[i].b))&1){
            c1++;
            cnt1.insert(i);
        }else{
            c2++;
            cnt2.insert(i);
        }
    }
    if(c1<=c2){
        cout<<"First"<<endl;
        while(c1!=0||c2!=0){
            if(c1!=0){
                cout<<*cnt1.begin()<<endl;
                c1--;
                cnt1.erase(*cnt1.begin());
            }else{
                cout<<*cnt2.begin()<<endl;
                c2--;
                cnt2.erase(*cnt2.begin());
            }
            if(c1==0&&c2==0)break;
            int x;cin>>x;
            if(cnt1.find(x)!=cnt1.end()){
                c1--;
                cnt1.erase(x);
            }
            else{
                c2--;
                cnt2.erase(x);
            }
        }
    }else{
        cout<<"Second"<<endl;
        while(c1!=0||c2!=0){
            int x;cin>>x;
            if(cnt1.find(x)!=cnt1.end()){
                c1--;
                cnt1.erase(x);
            }else{
                c2--;
                cnt2.erase(x);
            }
            if(c2!=0){
                cout<<*cnt2.begin()<<endl;
                c2--;
                cnt2.erase(*cnt2.begin());
            }else if(c1!=0){
                cout<<*cnt1.begin()<<endl;
                c1--;
                cnt1.erase(*cnt1.begin());
            }
        }
    }
}

F.

知识很多，放一点知识，整道题工程量有点大就先放着
2-sat
核心在建边操作
(a||b)
那么建边：g[a+n].push_back(b);
g[b+n].push_back(a);
查询问a和a+n所属强连通块是不是相同的，若是，则无解
不是，则有解，选择两者强连通块编号大的（拓扑序大）

动态开点线段树
与普通线段树的区别就是用这个点才开这个点
所以有左右节点数组

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
ll t[maxn<<1],lazy[maxn<<1];//因为是区间修改所以需要lazy
int lson[maxn<<1],rson[maxn<<1];
int cnt=1;//用于记录已使用的节点的数量
int n,m;

inline void Pushup(int &k){t[k]=t[lson[k]]+t[rson[k]];}
inline void Pushdown(int k,int l,int r){
    if(lazy[k]){
        if(!lson[k])lson[k]=++cnt;
        if(!rson[k])rson[k]=++cnt;
        //动态开点的Pushdown就这两句不一样——如果这个节点的子节点没有开，就把他申请开
        lazy[lson[k]]+=lazy[k];
        lazy[rson[k]]+=lazy[k];
        int mid=(l+r)>>1;

        t[lson[k]]+=(mid-l+1)*lazy[k];
        t[rson[k]]+=(r-mid)*lazy[k];
        lazy[k]=0;
    }
}
inline void build(int &k,int l,int r,int v,int x){//用单点修改的方式来建树
    if(!k)k=++cnt;//如上文所说，如果该节点不存在，就建立这个节点
    if(l==r)t[k]=x;
    else{
        int mid=(l+r)>>1;
        if(v<=mid)build(lson[k],l,mid,v,x);
        else build(rson[k],mid+1,r,v,x);
        Pushup(k);
    }
}
inline void update(int &k,int l,int r,int L,int R,int x){
    if(!k)k=++cnt;
    if(L<=l&&R>=r){
        lazy[k]+=x;t[k]+=(r-l+1)*x;
    }else{
        Pushdown(k,l,r);
        int mid=(l+r)>>1;
        if(L<=mid)update(lson[k],l,mid,L,R,x);
        if(R>mid)update(rson[k],mid+1,r,L,R,x);
        Pushup(k);
    }
}
inline ll query(int k,int l,int r,int L,int R){
    /*
        函数功能：查询数列中[L,R]区间内所有数之和
        变量解释：k:从update()中可以知道，如果一个节点不存在，那么它的左右儿子
                必然不存在，也就是说如果一个节点不存在，那它的值就是0而在查询时
                不需要新建节点，所以此处的k不需要引用
                L、R:需要查询的区间[L,R]
                l、r:当前节点的区间[l,r]
    */
    if(!k)return 0;
    if(L<=l&&R>=r)return t[k];
    Pushdown(k,l,r);
    int mid=(l+r)>>1;
    ll ans=0;
    if(L<=mid)ans+=query(lson[k],l,mid,L,R);
    if(R>mid)ans+=query(rson[k],mid+1,r,L,R);
    return ans;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x;int temp=1;
        scanf("%d",&x);
        build(temp,1,n,i,x);
    }
    for(int i=1;i<=m;i++){
        int q;
        scanf("%d",&q);
        if(q==1){
            int L,R,x;
            scanf("%d%d%d",&L,&R,&x);
            int temp=1;
            update(temp,1,n,L,R,x);
        }else{
            int L,R;
            scanf("%d%d",&L,&R);
            printf("%lld\n",query(1,1,n,L,R));
        }
    }
    return 0;
}

线段树建图
主要是点到区间或区间到点的连边，减少连边的数量
有两个线段树（一个入，一个出）

#include<bits/stdc++.h>
#define N 100010
#define M 300010
#define LOG 20
typedef int mainint;
#define int long long
using namespace std;
int lc[M*LOG],rc[M*LOG],tot,ncnt;
int n,m,s,rt1,rt2;

vector<pair<int,int>>g[M*LOG];
inline void addedge(int f,int t,int val){
    g[f].push_back({t,val});
    //nxt(++tot)=head[f];to(tot)=t;val(tot)=val;head[f]=tot;
}
void buildOut(int &o,int l,int r){//建出树
    if(l==r){
        o=l;return;//已经是子节点,直接赋值
    }o=++ncnt;
    int mid=(l+r)>>1;
    buildOut(lc[o],l,mid);buildOut(rc[o],mid+1,r);
    addedge(o,lc[o],0);//从o向o的左右子树连一条权值为0的有向边
    addedge(o,rc[o],0);
}
void buildIn(int &o,int l,int r){//建入树
    if(l==r){
        o=l;return;
    }
    o=++ncnt;
    int mid=(l+r)>>1;
    buildIn(lc[o],l,mid);buildIn(rc[o],mid+1,r);
    addedge(lc[o],o,0);//从o向o的左右子树连一条权值为0的有向边
    addedge(rc[o],o,0);
}
int L,R;
void update(int o,int l,int r,int f,int val,short type){
    if(L<=l && R>=r){
        type==2?addedge(f,o,val):addedge(o,f,val);
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid)update(lc[o],l,mid,f,val,type);
    if(R>mid)update(rc[o],mid+1,r,f,val,type);
}
const int inf=0x7fffffffffffffff;
int dis[M];
priority_queue< pair<int,int> > q;
int vis[M];
void dijkstra(int s){
    for(int i=1;i<=M;i++)dis[i]=inf,vis[i]=0;
    dis[s]=0;q.push(make_pair(0,s));
    while(q.size()){
        int x=q.top().second;q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int i=0;i<g[x].size();i++){
            int y=g[x][i].first,z=g[x][i].second;
            if(!vis[y]&&dis[y]>dis[x]+z){
                dis[y]=dis[x]+z;
                q.push(make_pair(-dis[y],y));
            }
        }
    }
}
inline int read(){
    int data=0,w=1;char ch=0;
    while(ch!='-' && (ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0' && ch<='9')data=data*10+ch-'0',ch=getchar();
    return data*w;
}
mainint main(){
    n=read();m=read();s=read();
    ncnt=n;//建边要求,线段树节点从n+1开始编号
    buildOut(rt1,1,n);buildIn(rt2,1,n);
    while(m--){
        int opt,f,t,val;
        opt=read();
        if(opt==1){
            f=read();t=read();val=read();
            addedge(f,t,val);//上面对叶子节点已经处理了,直接连边
        }else{
            f=read();L=read();R=read();val=read();
            update(opt==2?rt1:rt2,1,n,f,val,opt);
        }
    }
    dijkstra(s);
    for(int i=1;i<=n;i++)
        printf("%lld ",dis[i]<inf?dis[i]:-1);
    return 0;
}

标签：ch,val,33,void,iwtgm,mid,int,--
From： https://www.cnblogs.com/wwww-/p/17877867.html

相关文章

  • AtCoder Beginner Contest 331
    A-Tomorrow(abc331A)题目大意给定一年的月数和一月的天数，以及当天日期，问次日的日期。解题思路一个简单的进制加法运算，超出进制数则向前加一。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_st......
  • CF1833G Ksyusha and Chinchilla 题解
    题意：思路：当$n\not\equiv0\space(mod\space3)$时，无解；当$n\equiv0\space(mod\space3)$时，设$size_u$表示以$u$为根的子树还剩余的节点个数，自根节点向叶子节点递归，返回时进行处理节点$u$：设节点$u$的子节点为长度为$len$的序列$v$，设......
  • ABC331G 题解
    盒子里有\(n\)张\(m\)种卡片，第\(i\)种卡片有\(c_i\)张。\(\sumc_i=n\)。每次均匀随机选一张，再放回去。求拿出过的卡片包含全部种类所需要的取出次数的期望。对\(998244353\)取模。\(1\leqn,m\leq2e5,c_i\gt0\)。首先观察到，对于任意终止局面，最后取出的卡片一定......
  • AtCoder Beginner Contest 331
    AtCoderBeginnerContest331这场状态好差，下午的校赛也打的好差。A-Tomorrow#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve(){intM,D;inty,m,d;cin>>M>>D>>y>>m>&......
  • AtCoder Beginner Contest 331 G Collect Them All
    洛谷传送门AtCoder传送门设数字\(i\)第一次拿到的时间为\(t_i\)，所求即为\(E(\max\limits_{i=1}^mt_i)\)。施min-max容斥，有：\[\begin{aligned}E(\max\limits_{i=1}^mt_i)&=\sum\limits_{T\subseteq[1,m]\landT\ne\varnothing}(-1)^{|T|-1}E(\min\l......
  • AcWing 3302. 表达式求值
    题面：给定一个表达式，其中运算符仅包含加减乘除，可能包含括号，请你求出表达式的最终值。原题链接：3302.表达式求值-AcWing基本思路创建两个栈，分别存储数字和运算符运算符的判定：仅在以下条件满足时将运算符直接压入栈中：①栈中不存在元素②当前运算符优先级比栈顶高③栈顶为......
  • AtCoder Beginner Contest 331
    B-BuyOneCartonofMilk难度:⭐题目大意选择有三种套餐,6个鸡蛋S元,8个鸡蛋M元,12个鸡蛋L元;问如果要买至少N个鸡蛋,最少花费多少钱;解题思路一道入门级dp;神秘代码#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio(false......
  • [Codeforces] CF1733C Parity Shuffle Sorting
    题面翻译给定一个长度为\(n\)的数组，你可以对它进行不超过\(n\)次操作。对于每次操作：选择两个下标\(l,r\)，满足\(1\leql<r\leqn\)；若\(a_l+a_r\)为奇数，将\(a_r\)赋值为\(a_l\)，否则将\(a_l\)赋值为\(a_r\)。求一种方案，使得操作后的数组单调不减（即\(a_1\leq......
  • ABC331G题解
    ABC331G日常被bot吊打罢了。首先注意到一件事是你需要求一堆max的期望对吧。所以其实上来就应该试试上min-max容斥的。但是鉴于我没有脑子，所以其实没想到也可以理解。先来复习一下式子：\[Emax(S)=\sum_{T\subsetS}Emin(T)(-1)^{\midT\mid-1}\]所以带入要求的东西......
  • ABC 331 F - Palindrome Query(字符串哈希，树状数组)
    字符串哈希[OI-Wiki](字符串哈希-OIWiki(oi-wiki.org))分为两种哈希方式：以左为高位和以右为高位如果只是快速查询每个字串的哈希值，用以左为高位比较简单，即\[Hash[l...r]=Hash[1...r]-Hash[1...(l-1)]\timesbase^{r-l+1}\]但是如果有修改操作，需要将每一位的Hash值存......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99