## T1
区间修改+单点查询。差分树状数组。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN = 10000005; inline int rd(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return f?x:-x; } void out(int x){ if(!x) return; out(x/10); putchar('0'+x%10); } int f[MAXN],n,m,ans; void update(int x,int k){ for(;x<=n;x+=x&-x) f[x]+=k; } int query(int x){ int ret=0; for(;x;x-=x&-x) ret+=f[x]; return ret; } int main(){ // freopen("Agent3.in","r",stdin); // freopen("T1.out","w",stdout); n=rd(),m=rd(); int x,y,op; while(m--){ op=rd(); if(op==0) { x=rd();y=rd(); update(x,1);update(y+1,-1); } else{ x=rd();ans=query(x);if(!ans) putchar('0'); else out(query(x));putchar(' '); } } return 0; }
## T2
比赛的时候算错复杂度,以为是个模拟。拿了$60pts$的暴力分。正解要用双向链表,不太想写,留坑。
## T3
状压$dp$,考试的时候题意中有句话不理解,写了三份代码,结果发现都过不了大样例 ($wtf??$),最后快结束时瞎交了一份,结果拿了90。。最后发现中间有个地方没开$long long$ ,亏死。设$dp[S][i]$表示现在选的集合为$S$,最后一个选的为$i$的最大收益,然后再枚举一个集合外的元素$j$,进行转移。时间复杂度$O(2^n*n)$
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #define int long long using namespace std; const int MAXN = 20; typedef long long LL; inline int rd(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return f?x:-x; } int n,m,K,t[MAXN]; int val[MAXN],ex[MAXN][MAXN]; LL dp[1<<MAXN][MAXN],ans; inline void MAX(){ int S=0; for(register int i=1;i<=m;i++) S|=(1<<(t[i]-1)); for(register int i=1;i<=m;i++) ans=max(ans,dp[S][t[i]]); } void dfs(int x,int now){ if(now==m) {MAX();return;} if(x==n+1) return; t[now+1]=x;dfs(x+1,now+1); t[now+1]=0;dfs(x+1,now); } signed main(){ // memset(dp,-0x3f,sizeof(dp)); n=rd(),m=rd();K=rd();int x,y; for(register int i=1;i<=n;i++) val[i]=rd(); for(register int i=1;i<=K;i++){ x=rd(),y=rd(); ex[x][y]+=rd(); }dp[0][0]=0; for(register int i=1;i<=n;i++) dp[1<<(i-1)][i]=val[i]; for(register int S=0;S<1<<n;S++) for(register int i=1;i<=n;i++)if((S&(1<<(i-1)))) for(register int j=1;j<=n;j++)if(!(S&(1<<(j-1)))) dp[S|(1<<(j-1))][j]=max(dp[S|(1<<(j-1))][j],dp[S][i]+val[j]+ex[i][j]); // cout<<ans<<endl; dfs(1,0); cout<<ans<<endl; return 0; }