Noip模拟68 2021.10.4
2024-09-08 02:04:34
T1 玩水
成功在考试的时候注释掉正解，换成了暴力，只因为不敢保证正解思路的正确
脑子瓦特了，不知道把暴力打成函数拼在一起，不知道当时咋想的。。。。
就是你找有没有一个点上面和左面的字符一样，
如果这两个点有相邻关系或者包含关系就有解（包含关系是说一个点在另一个点的右下，不在同一行一列）
1 #include<bits/stdc++.h>
2 #define int long long
3 typedef unsigned long long ULL;
4 using namespace std;
5 namespace AE86{
6 inline int read(){
7 int x=0,f=1;char ch=getchar();
8 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
9 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
10 }inline void write(int x,char opt='\n'){
11 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
12 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
13 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
14 }using namespace AE86;
15 const int NN=1005;
16 int n,m,a[NN][NN],T;
17 char s[NN];
18 bool f[NN][NN];
19 namespace WSN{
20 inline short main(){
21 // freopen("in.in","r",stdin);
22 freopen("water.in","r",stdin);
23 freopen("water.out","w",stdout);
24 T=read();
25 while(T--){
26 n=read(); m=read(); memset(f,0,sizeof(f)); bool flag=0;
27 for(int i=1;i<=n;i++){
28 scanf("%s",s+1);
29 for(int j=1;j<=m;j++) a[i][j]=(s[j]-'a'+1);
30 }
31 for(int i=2;i<=n;i++) for(int j=2;j<=m;j++)
32 f[i][j]=(a[i-1][j]==a[i][j-1]);
33 for(int i=1;i<=n;i++){
34 for(int j=1;j<=m;j++) if(f[i][j]){
35 if(f[i+1][j]){flag=1;break;}
36 if(f[i][j+1]){flag=1;break;}
37 for(int k=i+1;k<=n;k++){
38 for(int u=j+1;u<=m;u++)
39 if(f[k][u]){flag=1;break;}
40 if(flag) break;
41 }
42 }
43 if(flag) break;
44 }
45 puts(flag?"1":"0");
46 }
47 return 0;
48 }
49 }
50 signed main(){return WSN::main();}
T2 假人
暴力的背包$dp$比较好打，但是正解目前还不会。。。
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 inline int read(){
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
9 }inline void write(int x,char opt='\n'){
10 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14 const int NN=1e5+5;
15 int n,k[NN],a[NN][6],tmp,rp;
16 inline void task1(){
17 int ans=0;
18 for(int i=1;i<=n;i++) ans+=a[i][1];
19 write(ans);
20 }
21 vector<pair<int,int> > pre;
22 int t,bin[NN*5],tot;
23 inline void dfs(int cnt){
24 if(cnt>n){
25 t=0;tot=0;
26 for(int i=0;i<pre.size();i++)
27 t+=pre[i].second,tot+=pre[i].first;
28 bin[t]=max(bin[t],tot);
29 return;
30 }
31 for(int i=1;i<=k[cnt];i++){
32 pre.push_back(make_pair(a[cnt][i],i));
33 dfs(cnt+1);
34 pre.pop_back();
35 }
36 }
37 inline void task2(){
38 dfs(1);
39 for(int i=n;i<=rp;i++) write(bin[i],' ');
40 puts("");
41 }
42 int f[3001][15005],sum;
43 inline void task3(){
44 sum=k[1];
45 for(int i=1;i<=k[1];++i) f[1][i]=a[1][i];
46 for(int i=2;i<=n;++i){
47 for(int j=i-1;j<=sum;++j)
48 for(int u=1;u<=k[i];++u)
49 f[i][j+u]=max(f[i][j+u],f[i-1][j]+a[i][u]);
50 sum+=k[i];
51 }
52 for(int i=n;i<=rp;i++) write(f[n][i],' '); puts("");
53 }
54 namespace WSN{
55 inline short main(){
56 freopen("fake.in","r",stdin);
57 freopen("fake.out","w",stdout);
58 n=read();
59 for(int i=1;i<=n;i++){
60 k[i]=read(); if(k[i]==1) ++tmp; rp+=k[i];
61 for(int j=1;j<=k[i];j++) a[i][j]=read();
62 }
63 if(tmp==n) return task1(),0;
64 if(n<=5) return task2(),0;
65 task3();
66 return 0;
67 }
68 }
69 signed main(){return WSN::main();}
TLE 40
T3 切题
比较隐含的线段树维护式子。
首先，暴力是网络流，（当然贪心也可以，但是不会太启发正解）
那么当他满流的时候就是合法的，考虑何时满流，满流的时候$maxflow=\sum\limits_{i=1}^{n}a_i$，把$a$从大到小排序的话
条件合法就会有$\forall k \in [0,n] \sum\limits_{i=1}^{k}a_i\leq \sum\limits_{i=1}^{m}\min(b_i,k)$
考虑优化，设$c_k$表示$b_i \geq k$的个数，那么$\sum\limits_{i=1}^{m}\min(b_i,k)=\sum\limits_{i=1}^{k}c_i$
那么合法的条件转化为$\forall k \in [0,n] \sum\limits_{i=1}^{k}(c_i-a_i) \geq 0$
我们用线段树维护这个式子的前缀和，下标为$k$，
考虑$1,2$操作，找到$a[x]$最后一次/第一次出现的位置，然后在线段树上区间修改即可（因为是维护前缀和）
可以用树状数组，可以用$\textit{upper_bound}$，不推荐后者，会调死，于是手打了$\textit{upper_bound}$
$3,4$操作直接考虑加减$b[x]$只会对$c_{b_x+1}，c_{b_x-1}$有影响，然而$c_{b[x]-1}$的影响不用考虑，在之前已经计算，所以直接修改后面的值即可。
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 inline int read(){
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
9 }inline void write(int x,char opt='\n'){
10 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14 const int NN=250005;
15 int n,m,a[NN],b[NN],q,sma,smb,c[NN],s[NN],tot;
16 struct BIT{
17 int tr[NN];
18 inline int lowbit(int x){return x&(-x);}
19 inline void update(int x,int v){for(int i=x+1;i;i-=lowbit(i))tr[i]+=v;}
20 inline int query(int x,int ans=0){for(int i=x+1;i<NN;i+=lowbit(i))ans+=tr[i];return ans;}
21 }t;
22 struct SNOWtree{
23 #define lid (id<<1)
24 #define rid (id<<1|1)
25 int mn[NN<<2],laz[NN<<2];
26 int ll[NN<<2],rr[NN<<2];
27 inline void build(int id,int l,int r){
28 ll[id]=l; rr[id]=r;if(l==r) return;
29 int mid=l+r>>1;
30 build(lid,l,mid); build(rid,mid+1,r);
31 }
32 inline void pushup(int id){
33 if(ll[id]==rr[id]) return;
34 mn[id]=min(mn[lid],mn[rid]);
35 }
36 inline void pushdown(int id){
37 if(laz[id]==0||ll[id]==rr[id]) return;
38 laz[lid]+=laz[id];laz[rid]+=laz[id];
39 mn[lid]+=laz[id]; mn[rid]+=laz[id];
40 laz[id]=0;
41 }
42 inline void insert(int id,int pos,int v){
43 if(ll[id]==rr[id]) {mn[id]=v;return;}
44 int mid=ll[id]+rr[id]>>1;
45 if(pos<=mid) insert(lid,pos,v);
46 else insert(rid,pos,v);
47 pushup(id);
48 }
49 inline void update(int id,int l,int r,int v){
50 if(l<=ll[id]&&rr[id]<=r){mn[id]+=v,laz[id]+=v;return;}
51 pushdown(id);int mid=ll[id]+rr[id]>>1;
52 if(l<=mid) update(lid,l,r,v);
53 if(r>mid) update(rid,l,r,v);
54 pushup(id);
55 }
56 }tr;
57 inline bool cmp(int a,int b){return a>b;}
58 inline int upper_bound(int x){
59 int l=1,r=n,ans=0;
60 while(l<=r){
61 int mid=l+r>>1;
62 if(s[mid]>x) l=mid+1,ans=mid;
63 else r=mid-1;
64 }
65 return ans;
66 }
67 namespace WSN{
68 inline short main(){
69 freopen("problem.in","r",stdin);
70 freopen("problem.out","w",stdout);
71 n=read(); m=read();
72 for(int i=1;i<=n;i++) a[i]=read(),sma+=a[i],s[i]=a[i];
73 for(int i=1;i<=m;i++) b[i]=read(),smb+=b[i],t.update(b[i],1);
74 sort(s+1,s+n+1,cmp); s[0]=1e18; s[n+1]=-1; tr.build(1,1,n);
75 for(int i=1;i<=n;i++) c[i]=t.query(i),tot+=c[i]-s[i],tr.insert(1,i,tot);
76 q=read(); int opt,x;
77 while(q--){
78 opt=read(),x=read();
79 if(opt==1){
80 int pos=upper_bound(a[x])+1; ++a[x];
81 ++s[pos];if(s[pos]>s[pos-1]) swap(s[pos],s[pos-1]);
82 tr.update(1,pos,n,-1);
83 }
84 if(opt==2){
85 int pos=upper_bound(a[x]-1); --a[x];
86 --s[pos];if(s[pos]<s[pos+1]) swap(s[pos],s[pos+1]);
87 tr.update(1,pos,n,1);
88 }
89 if(opt==3) tr.update(1,b[x]+1,n,1),++b[x];
90 if(opt==4) tr.update(1,b[x],n,-1),--b[x];
91 puts(tr.mn[1]>=0?"1":"0");
92 }
93 return 0;
94 }
95 }
96 signed main(){return WSN::main();}
T4 天下第一
$splay$都忘了，还要我写$LCT$？
于是还在学习$LCT$，并不会切
最新文章
- js学习笔记 （继续）
- 闲聊桌面应用开发[Win16->Win32->ATL/WTL/MFC->WinForm->WPF/Silverlight/WinRT]
- IDEA中，将文件夹加入classpath
- 百度文件上传webuploader上传文件，含文件大小、类型验证
- win7 64系统安装oracle客户端使用PL/SQL Developer工具
- Java_Swing实现小球沿正弦曲线运动的代码
- WAD Forwarder版USB Loader的安装和运行
- npm install 本地安装与全局安装
- Android蓝牙A2dp profile的使用
- OpenProcessToken令牌函数使用方法
- Servlet过滤器——异常捕获过滤器
- ajax处理跨域有几种方式
- git - 管理项目(SourceTree的使用)
- jenkins 修改log路径
- sed 详解【转】
- 基于 Redis 做分布式锁
- 【UOJ#67】新年的毒瘤(Tarjan)
- WCF的简单使用
- react notes
- SESSION机制（转）