# 2017/07/25 杂题（完全不可做题（划去））选讲

cogs2421 简单的Treap

1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 const int maxn=500005;
7 int n,lc[maxn],rc[maxn],stack[maxn],top,root;
8 struct node
9 {
10     int val,fix;
11     bool operator <(const node b)const{
12         return val<b.val;
13     }
14 }a[maxn];
15 void dfs(int root)
16 {
17     printf("%d ",a[root].val);
18     if(lc[root])dfs(lc[root]);
19     if(rc[root])dfs(rc[root]);
20 }
21 int main()
22 {
23     freopen("treap.in","r",stdin);
24     freopen("treap.out","w",stdout);
25     int __size__=128<<20;
26     char *__p__=(char*)malloc(__size__)+__size__;
27     __asm__("movl %0, %%esp\n"::"r"(__p__));
28     scanf("%d",&n);
29     for(int i=1;i<=n;i++)scanf("%d",&a[i].val);
30     for(int i=1;i<=n;i++)scanf("%d",&a[i].fix);
31     sort(a+1,a+n+1);
32     for(int i=1;i<=n;i++)
33     {
34         stack[top+1]=0;
35         while(top&&a[stack[top]].fix>a[i].fix)top--;
36         lc[i]=stack[top+1];
37         (top?rc[stack[top]]:root)=i;
38         stack[++top]=i;
39     }
40     dfs(root);
41 }

cogs2421

cogs2434 暗之链锁

1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<vector>
6 using namespace std;
7 const int maxn=100005,maxm=200005;
8 vector<int>G[maxn],q[maxn];
9 int n,m,prt[maxn],anc[maxn],a[maxn],x,y,ans;
10 bool vis[maxn];
11 int findroot(int x)
12 {
13     return anc[x]==x?x:(anc[x]=findroot(anc[x]));
14 }
15 void dfs1(int x)
16 {
17     int cnt=G[x].size();
18     anc[x]=x;
19     for(int i=0;i<cnt;i++)
20         if(G[x][i]!=prt[x])
21         {
22             prt[G[x][i]]=x;
23             dfs1(G[x][i]);
24         }
25     vis[x]=1;cnt=q[x].size();
26     for(int i=0;i<cnt;i++)
27         if(vis[q[x][i]])a[findroot(q[x][i])]-=2;
28     anc[x]=prt[x];
29 }
30 void dfs2(int x)
31 {
32     int cnt=G[x].size();anc[x]=x;
33     for(int i=0;i<cnt;i++)
34         if(G[x][i]!=prt[x])
35         {
36             dfs2(G[x][i]);
37             a[x]+=a[G[x][i]];
38         }
39     if(prt[x])
40         if(!a[x])ans+=m;
41         else if(a[x]==1)ans++;
42 }
43 int haha()
44 {
45     freopen("yam.in","r",stdin);
46     freopen("yam.out","w",stdout);
47     scanf("%d%d",&n,&m);
48     for(int i=1;i<n;i++)
49     {
50         scanf("%d%d",&x,&y);
51         G[x].push_back(y);G[y].push_back(x);
52     }
53     for(int i=0;i<m;i++)
54     {
55         scanf("%d%d",&x,&y);
56         if(x==y)continue;
57         a[x]++;a[y]++;
58         q[x].push_back(y),q[y].push_back(x);
59     }
60     dfs1(1);dfs2(1);
61     printf("%d\n",ans);
62     //while(1);
63 }
64 int sb=haha();
65 int main(){;}

cogs2434

HEOI2017 组合数问题

NOI2016区间

1 #include<iostream>
2 #include<cstring>
3 #include<algorithm>
4 #include<cstdio>
5 using namespace std;
6 const int maxn=1000005;
7 int n,m,x,sm[maxn<<2],mx[maxn<<2],b[maxn],p[maxn],cnt;
8 struct districts
9 {
10     int l,r,len;
11 }ques[maxn];
12 int cmp(const int &a,const int &b)
13 {
14     return ques[a].len<ques[b].len;
15 }
16 #define mid ((l+r)>>1)
17 #define lson root<<1,l,mid
18 #define rson root<<1|1,mid+1,r
19 #define lc root<<1
20 #define rc root<<1|1
21 void Modify(int root,int l,int r,int L,int R,int val)
22 {
23     if(L<=l&&r<=R)
24     {
25         mx[root]+=val;
26         sm[root]+=val;
27         return;
28     }
29     if(mid>=L)Modify(lson,L,R,val);
30     if(mid<R)Modify(rson,L,R,val);
31     mx[root]=max(mx[lc],mx[rc])+sm[root];
32 }
33 int haha()
34 {
35     freopen("interval.in","r",stdin);
36     freopen("interval.out","w",stdout);
37     scanf("%d%d",&n,&m);
38     for(int i=1;i<=n;i++)
39     {
40         p[i]=i;districts &d=ques[i];
41         scanf("%d%d",&d.l,&d.r);
42         d.len=d.r-d.l+1;
43         b[++cnt]=d.l;b[++cnt]=d.r;
44     }
45     sort(p+1,p+n+1,cmp);sort(b+1,b+cnt+1);
46     cnt=unique(b+1,b+cnt+1)-b-1;
47     for(int i=1;i<=n;i++)
48     {
49         int t=p[i];districts &d=ques[t];
50         d.l=lower_bound(b+1,b+cnt+1,d.l)-b;
51         d.r=lower_bound(b+1,b+cnt+1,d.r)-b;
52     }
53     int ans=0x7f7f7f7f;
54     for(int i=1,j=0;j<n||(mx[1]==m&&j==n);)
55     {
56         while(mx[1]<m&&j<n)
57         {
58             j++;
59             Modify(1,1,cnt,ques[p[j]].l,ques[p[j]].r,1);
60         }
61         while(mx[1]==m&&i<=n)
62         {
63             ans=min(ans,ques[p[j]].len-ques[p[i]].len);
64             Modify(1,1,cnt,ques[p[i]].l,ques[p[i]].r,-1);
65             i++;
66         }
67     }
68     if(ans==0x7f7f7f7f)ans=-1;
69     printf("%d\n",ans);
70 }
71 int sb=haha();
72 int main(){;}

cogs2406

ZJOI2004 树的果实

HNOI2016 序列

cogs2582 动物城的鸳鸯蛋传说

bitset第一题……

1 http://cogs.pro/cogs/problem/problem.php?pid=2582

cogs2582

cogs2089 平凡的测试数据

cogs1000 伊吹萃香

NOI2014 起床困难综合症

1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 int haha()
7 {
8     freopen("sleep.in","r",stdin);
9     freopen("sleep.out","w",stdout);
10     int n,m;scanf("%d%d",&n,&m);
11     int id,ide=0;for(id=1;id<m;id=id<<1|1);
12     for(int i=1;i<=n;i++)
13     {
14         char opt[5];int v;scanf("%s%d",opt,&v);
15         switch(opt[0])
16         {
17             case ‘O‘:ide|=v;id|=v;break;
18             case ‘X‘:ide^=v;id^=v;break;
19             case ‘A‘:ide&=v;id&=v;break;
20         }
21     }
22     bool judge=0;int q=0;
23     for(int i=29;i>=0;i--)
24     {
25         int t=ide>>i&1;
26         if((judge||(m>>i&1))&&(id>>i&1)>t)t=id>>i&1;
27         if(m>>i&1)judge=1;
28         q|=t<<i;
29     }
30     printf("%d\n",q);
31 }
32 int sb=haha();
33 int main(){;}

cogs1684

cogs2235 烤鸡翅

HEOI2017 期末考试

1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 typedef long long LL;
7 const int maxn=100005;
8 int A,B,C;int n,m,t[maxn],b[maxn];
9 LL work(int val)
10 {
11     LL res=0,v1=0,v2=0;
12     for(int i=1;i<=n;i++)
13         if(val>t[i])res+=(LL)(val-t[i])*C;
14     for(int i=1;i<=m;i++)
15         if(b[i]<val)v1+=val-b[i];
16         else v2+=b[i]-val;
17     if(A>=B)res+=(LL)v2*B;
18     else
19     {
20         res+=(LL)min(v1,v2)*A;
21         if(v1<v2) res+=(LL)(v2-v1)*B;
22     }
23     return res;
24 }
25 int haha()
26 {
27     scanf("%d%d%d",&A,&B,&C);
28     scanf("%d%d",&n,&m);
29     int maxx=0;
30     for(int i=1;i<=n;i++)scanf("%d",&t[i]);
31     for(int i=1;i<=m;i++)scanf("%d",&b[i]);
32     int l=0,r=100000;
33     LL ans=1e18;
34     while(r-l>5)
35     {
36         int mid=l+(r-l)/3,midmid=r-(r-l)/3;
37         LL v1=work(mid),v2=work(midmid);
38         if(v1<=v2)
39         {
40             ans=min(ans,v1);
41             r=midmid;
42         }
43         else
44         {
45             ans=min(ans,v2);
46             l=mid;
47         }
48     }
49     for(int i=l;i<=r;i++)ans=min(ans,work(i));
50     printf("%lld\n",ans);
51 }
52 int sb=haha();
53 int main(){;}

bzoj4869

51nod1597 有限背包计数问题

cogs1825 道路和航线

1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<vector>
6 #include<queue>
7 using namespace std;
8 const int maxt=25005,maxr=50005;
9 struct node
10 {
11     int from,to,weight,next;
12 }edge1[maxr<<1];
14 void addedge1(int u,int v,int w)
15 {
17 }
18 vector<int>a[maxt];
19 int id[maxt];
20 void dfs1(int x)
21 {
22     id[x]=cnt;a[cnt].push_back(x);
24         if(!id[edge1[i].to])dfs1(edge1[i].to);
25 }
26 vector<int>G[maxt],W[maxt],G2[maxt];
27 int entrance_degree[maxr];
28 bool vis[maxr];
29 void dfs2(int x)
30 {
31     vis[x]=1;
32     for(int i=0;i<G2[x].size();i++)
33     {
34         entrance_degree[G2[x][i]]++;
35         if(!vis[G2[x][i]])dfs2(G2[x][i]);
36     }
37 }
38 struct point
39 {
40     int dis,id;
41     bool operator <(const point &b)const{
42         return dis>b.dis;
43     }
44 };
45 priority_queue<point>heap;
46 int dist[maxt];
47 void Dijkstra()
48 {
49     while(!heap.empty())
50     {
51         point tmp=heap.top();heap.pop();
52         int dis=tmp.dis,iden=tmp.id;
53         if(vis[iden])continue;
54         vis[iden]=1;
56         {
57             int v=edge1[i].to;
58             if(dist[v]>dist[iden]+edge1[i].weight)
59             {
60                 dist[v]=dist[iden]+edge1[i].weight;
61                 heap.push((point){dist[v],v});
62             }
63         }
64     }
65 }
66 void bfs()
67 {
68     memset(vis,0,sizeof(vis));
69     memset(dist,63,sizeof(dist));
70     queue<int>q;q.push(id[s]);dist[s]=0;
71     while(!q.empty())
72     {
73         int x=q.front();q.pop();
74         for(int i=0;i<a[x].size();i++)
75             if(dist[a[x][i]]<0x3f3f3f3f)heap.push((point){dist[a[x][i]],a[x][i]});
76         Dijkstra();
77         for(int i=0;i<a[x].size();i++)
78             for(int j=0;j<G[a[x][i]].size();j++)
79             {
80                 dist[G[a[x][i]][j]]=min(dist[G[a[x][i]][j]],dist[a[x][i]]+W[a[x][i]][j]);
81                 if(!--entrance_degree[id[G[a[x][i]][j]]])q.push(id[G[a[x][i]][j]]);
82             }
83     }
84 }
85 int haha()
86 {
89     scanf("%d%d%d%d",&t,&r,&p,&s);
90     for(int i=1;i<=r;i++)
91     {
92         int u,v,w;scanf("%d%d%d",&u,&v,&w);
94     }
95     for(int i=1;i<=t;i++)
96         if(!id[i])
97         {
98             cnt++;
99             dfs1(i);
100         }
101     for(int i=1;i<=p;i++)
102     {
103         int x,y,z;scanf("%d%d%d",&x,&y,&z);
104         G[x].push_back(y);
105         W[x].push_back(z);
106         G2[id[x]].push_back(id[y]);
107     }
108     dfs2(id[s]);
109     bfs();
110     for(int i=1;i<=t;i++)
111         if(dist[i]==0x3f3f3f3f)puts("NO PATH");
112         else printf("%d\n",dist[i]);
113 }
114 int sb=haha();
115 int main(){;}

cogs1825

HEOI2016 排序

1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #define lson root<<1,l,mid
6 #define rson root<<1|1,mid+1,r
7 #define lc root<<1
8 #define rc root<<1|1
9 using namespace std;
10 const int maxn=100005;
11 int sm[maxn<<2],st[maxn<<2],a[maxn];
12 void Build(int root,int l,int r,int val)
13 {
14     st[root]=-1;
15     if(l==r)
16     {
17         if(a[l]>=val)sm[root]=1;
18         else sm[root]=0;
19         return;
20     }
21     int mid=(l+r)>>1;
22     Build(lson,val);Build(rson,val);
23     sm[root]=sm[lc]+sm[rc];
24 }
25 void pushdown(int root,int l,int r)
26 {
27     if(l==r)return;
28     if(st[root]!=-1)
29     {
30         st[lc]=st[rc]=st[root];
31         int mid=(l+r)>>1;
32         sm[lc]=st[lc]*(mid-l+1);
33         sm[rc]=st[rc]*(r-mid);
34         st[root]=-1;
35     }
36 }
37 void pushup(int root)
38 {
39     sm[root]=sm[lc]+sm[rc];
40 }
41 int Query(int root,int l,int r,int L,int R)
42 {
43     if(L<=l&&r<=R)return sm[root];
44     pushdown(root,l,r);
45     int mid=(l+r)>>1,ans=0;
46     if(R<=mid)ans=Query(lson,L,R);
47     else if(L>mid)ans=Query(rson,L,R);
48     else
49     {
50         ans+=Query(lson,L,mid);
51         ans+=Query(rson,mid+1,R);
52     }
53     return ans;
54 }
55 void Set(int root,int l,int r,int L,int R,int val)
56 {
57     if(L>R)return;
58     if(L<=l&&r<=R)
59     {
60         st[root]=val;
61         sm[root]=val*(r-l+1);
62         return;
63     }
64     int mid=(l+r)>>1;
65     pushdown(root,l,r);
66     if(R<=mid)Set(lson,L,R,val);
67     else if(L>mid)Set(rson,L,R,val);
68     else
69     {
70         Set(lson,L,mid,val);
71         Set(rson,mid+1,R,val);
72     }
73     pushup(root);
74 }
75 int n,m,q;
76 struct Ques
77 {
78     int l,r,val;
79 }qu[maxn];
80 bool Check(int val)
81 {
82     Build(1,1,n,val);
83     for(int i=1;i<=m;i++)
84     {
85         int wal=Query(1,1,n,qu[i].l,qu[i].r);
86         int fenjiexian;
87         if(qu[i].val)
88         {
89             fenjiexian=qu[i].l+wal-1;
90             Set(1,1,n,qu[i].l,fenjiexian,1);
91             Set(1,1,n,fenjiexian+1,qu[i].r,0);
92         }
93         else
94         {
95             fenjiexian=qu[i].r-wal+1;
96             Set(1,1,n,qu[i].l,fenjiexian-1,0);
97             Set(1,1,n,fenjiexian,qu[i].r,1);
98         }
99     }
100     int k=Query(1,1,n,q,q);
101     if(k)return 1;
102     else return 0;
103 }
104 int haha()
105 {
106     freopen("heoi2016_sort.in","r",stdin);
107     freopen("heoi2016_sort.out","w",stdout);
108     scanf("%d%d",&n,&m);
109     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
110     for(int i=1;i<=m;i++)scanf("%d%d%d",&qu[i].val,&qu[i].l,&qu[i].r);
111     scanf("%d",&q);
112     int l=1,r=n,ans;
113     while(l<=r)
114     {
115         int mid=(l+r)>>1;
116         if(Check(mid))
117             l=mid+1;
118         else r=mid-1;
119     }
120     printf("%d\n",r);
121 }
122 int sb=haha();
123 int main(){;}

cogs2276

Tower

（所以这么多坑我填的完么……）

## 做题细节

1. 如果题目是枚举的话,即最后化成十分简单的形式比较小, 可以直接将各种不同状态的结果运算过程写出来,但是这并不见得比写函数要快多少 而且比较容易出错,比如下标没有更改之类,这种错误比较烦人,因为你会查看算法, 但是算法本身并没有错误,所以如果复制粘贴的话,注意不同情况的不同点,如果自己 不够细心,最好写成函数的形式(注意判断边界),以防出错.//16:35 2004-4-17 2. 在编程之后检查的第一件事就是初始化, 你的初始化也许写在循环体之外,故只能AC一组测试数据,sample. /

## bzoj5108 [CodePlus2017]可做题 位运算dp+离散

[CodePlus2017]可做题 Time Limit: 10 Sec  Memory Limit: 512 MBSubmit: 87  Solved: 63[Submit][Status][Discuss] Description qmqmqm希望给sublinekelzrip出一道可做题.于是他想到了这么一道题目:给一个长度为n的非负整数序列ai,你需 要计算其异或前缀和bi,满足条件b1=a1,bi=bi?1 xor ai(i≥2).但是由于数据生成器出现了问题,他生成的序列a 的长度特

## 暑假做题记录【实时更新】

2017.7.6 POJ 3264[RMQ板子题,话说线段树也可以做,并且很简单] BZOJ 1303,1012,2257,2748,1088 比赛未做的三题补题 2017.7.7 待续...........................................................................................

## 2017.11.25【NOIP提高组】模拟赛A组

2017.11.25[NOIP提高组]模拟赛A组 T1 3467. [NOIP2013模拟联考7]最长上升子序列(lis) T2 3468. [NOIP2013模拟联考7]OSU!(osu) T3 3472. [NOIP2013模拟联考8]匹配(match) T1 有转移方程f[i]=max{f[j]}+1,a[j]<a[i] 可以用线段树+离散化维护这个方程,因为涉及以往状态可以用主席树维护 打太丑爆空间了 Code 1 #include<cstdio> 2 #include<c