菜得过分。
面对T1的大板子不知所措，然后T2的贪心不小心把排序语句删了。。。
T1这种大模板啊。。。其实我是觉得我能打出来的，然后先用一个小时码了一个2k。
然后做T2想贪心就出来了。十分钟码完T3暴力之后回T1打对拍瞬间爆炸。
于是又重新打了一个2k，WA0。对拍发现。
然后考试就没几分钟了交暴力走了。
不要打完就跑，记得早点对拍改进思路。
T1：
的确是挺裸的线段树。离散化或者权值线段树都可以。
但是考场上两个都打出来都死了。
最后用离散化A的。
1 #include<cstdio>
2 #include<unordered_map>
3 #include<algorithm>
4 using namespace std;
5 #define inf 10000001
6 unordered_map<long long,int>M;
7 int m,cnt,k[100005];long long x[300005],l[100005],r[100005],re[300005];
8 struct Segment_Tree{
9 int cl[1500005],cr[1500005],lz[1500008],lzxor[1500008],w0[1500008],w1[1500008];
10 void build(int p,int l,int r){
11 cl[p]=l;cr[p]=r;lz[p]=-1;w0[p]=l;w1[p]=inf;
12 if(l==r)return;
13 build(p<<1,l,l+r>>1);build(p<<1|1,(l+r>>1)+1,r);
14 }
15 void up(int p){w0[p]=min(w0[p<<1],w0[p<<1|1]);w1[p]=min(w1[p<<1],w1[p<<1|1]);}
16 void down(int p){
17 if(lz[p]!=-1){
18 lz[p<<1]=lz[p],lz[p<<1|1]=lz[p];
19 lzxor[p<<1]=lzxor[p<<1|1]=0;
20 if(lz[p])w1[p<<1]=cl[p<<1],w1[p<<1|1]=cl[p<<1|1],w0[p<<1]=w0[p<<1|1]=inf;
21 else w1[p<<1]=w1[p<<1|1]=inf,w0[p<<1]=cl[p<<1],w0[p<<1|1]=cl[p<<1|1];
22 lz[p]=-1;
23 }else if(lzxor[p]){
24 if(lz[p<<1]!=-1)lz[p<<1]^=1;else lzxor[p<<1]^=1;
25 if(lz[p<<1|1]!=-1)lz[p<<1|1]^=1;else lzxor[p<<1|1]^=1;
26 swap(w1[p<<1],w0[p<<1]);
27 swap(w1[p<<1|1],w0[p<<1|1]);
28 lzxor[p]=0;
29 }
30 up(p);
31 }
32 void set(int p,int l,int r,int w){
33 if(l<=cl[p]&&cr[p]<=r){
34 lz[p]=w;lzxor[p]=0;
35 if(w)w1[p]=cl[p],w0[p]=inf;
36 else w1[p]=inf,w0[p]=cl[p];
37 return;
38 }
39 down(p);
40 if(l<=cr[p<<1])set(p<<1,l,r,w);
41 if(r>=cl[p<<1|1])set(p<<1|1,l,r,w);
42 up(p);
43 }
44 void Xor(int p,int l,int r){
45 if(l<=cl[p]&&cr[p]<=r){
46 if(lz[p]!=-1)lz[p]^=1;else lzxor[p]^=1;
47 swap(w0[p],w1[p]);
48 return;
49 }
50 down(p);
51 if(l<=cr[p<<1])Xor(p<<1,l,r);
52 if(r>=cl[p<<1|1])Xor(p<<1|1,l,r);
53 up(p);
54 }
55 }Tree;
56 main(){
57 scanf("%d",&m);
58 for(int i=1;i<=m;++i)scanf("%d%lld%lld",&k[i],&l[i],&r[i]),x[i]=l[i],x[m+i]=r[i],x[m+m+i]=r[i]+1;
59 sort(x+1,x+1+m+m+m);
60 for(int i=1;i<=m*3;++i)if(x[i]!=x[i-1])M[x[i]]=++cnt,re[cnt]=x[i];
61 for(int i=1;i<=m;++i)l[i]=M[l[i]],r[i]=M[r[i]];
62 if(M.find(1)==M.end()){for(int i=1;i<=m;++i)puts("1");return 0;}
63 Tree.build(1,1,cnt);Tree.lz[1]=0;
64 for(int i=1;i<=m;++i){
65 if(k[i]==1)Tree.set(1,l[i],r[i],1);
66 if(k[i]==2)Tree.set(1,l[i],r[i],0);
67 if(k[i]==3)Tree.Xor(1,l[i],r[i]);
68 printf("%lld\n",re[Tree.w0[1]]);
69 }
70 }
View Code
思路积累：
- 线段树模板
T2：
三分其实不完全正确。虽然secret证明了单峰性质，但是ooo给出了函数值在谷底以外的地方不严格单调的例子。
直接贪心的话我们会发现决策有点复杂而且还可能会反悔。
但是其实只有四种物品，它们内部先排一下序（一定要排序啊啊啊）
根据数据范围的提示，两人都喜欢的物品是特殊的。
然后如果我们确定了两人都喜欢的物品的选择数量，剩下的贪心决策就好说了。
总费用关于它是个单峰函数（非严格）。
注意左右端点。
1 #include<cstdio>
2 #include<algorithm>
3 using namespace std;
4 struct ps{
5 int c1,c2;long long v;
6 friend bool operator<(ps a,ps b){return a.v<b.v;}
7 }p[100005];
8 int n,m,k,a,b,n0,n1,n2,n3;long long v[100005],c1[100005],c2[100005];
9 long long q0[100005],q1[100005],q2[100005],q3[100005],ans=100000000000000000ll;
10 long long chk(int p){
11 long long tot=0,lft=m-k-(k-p);
12 for(int i=1;i<=p;++i)tot+=q3[i];
13 for(int j=1;j<=k-p;++j)tot+=q1[j]+q2[j];
14 int p0=1,p1=k-p+1,p2=k-p+1;
15 while(lft--)
16 if(q0[p0]<q1[p1]&&q0[p0]<q2[p2])tot+=q0[p0],p0++;
17 else if(q1[p1]<q2[p2])tot+=q1[p1],p1++;
18 else tot+=q2[p2],p2++;
19 ans=min(ans,tot);//printf("%d %lld\n",p,tot);
20 return tot;
21 }
22 main(){
23 scanf("%d%d%d",&n,&m,&k);
24 for(int i=1;i<=n;++i)scanf("%lld",&v[i]);
25 scanf("%d",&a);for(int i=1,x;i<=a;++i)scanf("%d",&x),c1[x]=1;
26 scanf("%d",&b);for(int i=1,x;i<=b;++i)scanf("%d",&x),c2[x]=1;
27 for(int i=1;i<=n;++i)
28 if(c1[i]&&c2[i])q3[++n3]=v[i];
29 else if(c1[i])q1[++n1]=v[i];
30 else if(c2[i])q2[++n2]=v[i];
31 else q0[++n0]=v[i];
32 sort(q0+1,q0+n0+1);
33 sort(q1+1,q1+n1+1);
34 sort(q2+1,q2+n2+1);
35 sort(q3+1,q3+n3+1);
36 q0[n0+1]=q1[n1+1]=q2[n2+1]=1000000000000ll;
37 int l=0,r=n3;
38 l=max(l,max(k-n1,k-n2));l=max(l,2*k-m);//printf("%d %d\n",l,r);
39 if(l>r){puts("-1");return 0;}
40 while(l<r-1)if(chk(l+r>>1)<chk((l+r>>1)+1))r=l+r>>1;else l=l+r>>1;
41 for(int i=l;i<=r;++i)chk(i);
42 printf("%lld\n",ans);
43 }
View Code
- 贪心
- 单峰函数三分
- 这两个知识点总在一起出现？
T3：
见下发题解。
挺神仙的。
1 #include<cstdio>
2 #include<bitset>
3 using namespace std;
4 bitset<401>B[401];
5 int n,m,a[50005],b[50005],ans;
6 int main(){
7 scanf("%d%d",&n,&m);
8 for(int i=1;i<=m;++i)scanf("%d%d",&a[i],&b[i]);
9 for(int i=1;i<=n;++i)B[i][i]=1;
10 for(int i=1;i<=n;++i)for(int j=m;j;--j)
11 if(B[i][a[j]]&&B[i][b[j]]){B[i].reset();break;}
12 else if(B[i][a[j]]&&!B[i][b[j]])B[i][b[j]]=1;
13 else if(B[i][b[j]]&&!B[i][a[j]])B[i][a[j]]=1;
14 for(int i=1;i<=n;++i)if(B[i].any())for(int j=i+1;j<=n;++j)if(B[j].any()&&(B[i]&B[j]).none())ans++;
15 printf("%d\n",ans);
16 }
View Code
什么时候才能回到原来的状态啊。。。
为什么会这么菜啊。。。
可是我好像会做啊。。。