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;
}