2017/8/8 考试吐槽

2017 8 8 得分：120

麻麻我a题啦哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈……（快拖出去又疯一个）

不废话了直接开始今天的吐槽……

a、Evensgn 的债务

题意：几个人来回欠钱，找到一种方式使流动的钱最少。

啊……上次考试a题还是什么时候……我想想……大概是刚开始学习语法的时候吧……换句话说十个月考试没有a题了……这种感觉真特么爽……

考试时候刚开始思博地认为是个图论，推了一会发现不对！卧槽这不是我那本小学生益智游戏原题么！那道题的答案我死都忘不掉！每个人都把钱扔地上，欠钱的自己扔，要钱的自己捡，最后每个要账的人净收入之和不就是最后答案么！妈的思博题.png……妈的智障.png……5分钟走人……

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cstdlib>
 6 using namespace std;
 7 const int maxn=1e6+5;
 8 struct node
 9 {
10     int from,to,weight,next;
11 }edge[maxn];
12 int head[maxn],tot,IN[maxn];
13 bool vis[maxn];
14 void addedge(int u,int v,int w)
15 {
16     edge[++tot]=(node){u,v,w,head[u]};head[u]=tot;
17 }
18 int n,m;
19 int tmp;
20 void dfs(int root)
21 {
22     vis[root]=1;
23     for(int i=head[root];i;i=edge[i].next)
24     {
25         int v=edge[i].to;
26         IN[v]+=edge[i].weight;
27         IN[root]-=edge[i].weight;
28         if(!vis[v])dfs(v);
29     }
30 }
31 int haha()
32 {
33     scanf("%d%d",&n,&m);
34     for(int i=1;i<=m;i++)
35     {
36         int x,y,z;scanf("%d%d%d",&x,&y,&z);
37         addedge(x,y,z);
38     }
39     int ans=0;
40     for(int i=1;i<=n;i++)
41         if(!vis[i])dfs(i);
42     for(int i=1;i<=n;i++)
43         if(IN[i]>0)ans+=IN[i];
44     printf("%d
",ans);
45 }
46 int sb=haha();
47 int main(){;}

B、Number

题意：一个排列，求出了$a$数组，元素为这个东西左边比它小的数的个数，求原数列。

由于第一题太水，麻痹大意结果被教做人……只看出来越往右越小然而并不会实现……

实际上我的想法是对的，正解就是不断地寻找最右端的$0$，然后把这个数设置为当前最小的数，随后这个数右面区间全部$-1$。

为什么这样是对的呢？我们考虑一下最小值：如果说最小值没有出现在最右端的$0$，那么必然会有另一个更小的出现在右面，不然那个数字就绝对不会是$0$。于是任务就变成了找最右端的$0$，思博数据结构。听说$dalao$们都写了$Treap/Splay$，只会线段树的萌新鏼鏼发抖……

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<set>
 6 using namespace std;
 7 const int maxn=100005,inf=2147483647;
 8 int n,a[maxn],xingzhuang[maxn];
 9 int mn[maxn<<2],st[maxn<<2];
10 #define mid ((l+r)>>1)
11 #define lc root<<1
12 #define rc root<<1|1
13 #define lson lc,l,mid
14 #define rson rc,mid+1,r
15 void update(int root)
16 {
17     mn[root]=min(mn[lc],mn[rc]);
18 }
19 void build(int root,int l,int r)
20 {
21     if(l==r)
22     {
23         mn[root]=xingzhuang[l];
24         return;
25     }
26     build(lson),build(rson);
27     update(root);
28 }
29 void pushdown(int root)
30 {
31     if(st[root])
32     {
33         st[lc]+=st[root];
34         st[rc]+=st[root];
35         mn[lc]+=st[root];
36         mn[rc]+=st[root];
37         st[root]=0;
38     }
39 }
40 int query(int root,int l,int r)
41 {
42     //cout<<mn[root]<<endl;
43     if(mn[root])return 1;
44     if(l==r)return l;
45     pushdown(root);
46     if(mn[rc]==mn[root])return query(rson);
47     else return query(lson);
48 }
49 void Change(int root,int l,int r,int pos,int val)
50 {
51     if(l==r)
52     {
53         mn[root]=val;
54         st[root]=0;
55         return;
56     }
57     pushdown(root);
58     if(pos<=mid)Change(lson,pos,val);
59     else Change(rson,pos,val);
60     update(root);
61 }
62 void Modify(int root,int l,int r,int L,int R,int val)
63 {
64     if(L<=l&&r<=R)
65     {
66         mn[root]+=val;
67         st[root]+=val;
68         return;
69     }
70     pushdown(root);
71     if(L<=mid)Modify(lson,L,R,val);
72     if(R>mid)Modify(rson,L,R,val);
73     update(root);
74 }
75 int haha()
76 {
77     scanf("%d",&n);xingzhuang[1]=n;
78     for(int i=2;i<=n;i++)scanf("%d",&xingzhuang[i]);
79     build(1,1,n);
80     for(int i=1;i<=n;i++)
81     {
82         int pos=query(1,1,n);
83         a[pos]=i;
84         Change(1,1,n,pos,inf);
85         Modify(1,1,n,pos,n,-1);
86         //cout<<pos+1<<endl;
87     }
88     for(int i=1;i<=n;i++)printf("%d
",a[i]);
89 }
90 int sb=haha();
91 int main(){;}

C、与非

题意：给出一个动态与非门逻辑电路，不断插入新的输入节点，同时不断查询区间内所有输出的异或结果。强制在线。

日常爆零……没什么说的了……我竟然这种思博题暴力都拿不了……

官方的标算是线段树动态维护……然而$lc$ 神犇想出来了一个怒踩标程$1500ms$的线性算法……

下面开始$Ctrl+C$ $lc$ 题解

$nand[ i ,j ]$定义同题面。那么$nand[i，j]=!(nand[ i , j-1 ]&a[ j ]) =……(!a[ i ]& a [ i+1])&…….$
$f[ i ]$表示$nand[ 1,i ]$。$f[ j ]=…… !((! f[i-1]&a [i ]）&a[ i+1 ])……$
观察上下两式。
$f[j]$与$nand[ i ,j ]$结果仅决定于$!(a[ i ]& a [ i+1])$与$!((! f[i-1]&a [i ])&a[ i+1 ]))$。分类讨论一下，当$a[i+1 ]==0$时，两式结果相等，当$a[i+1 ]==1$时，那么仅在
$(a[ i ]==1&&f[i-1]==1)||(a[i]==0)$时对答案可能产生影响。前者使这一层变成$0$与$1$，后者使这一层变成$1$与$0$ 。然后，数据就卡不到了呗。

（具体不太好写，我在下面写一下式子）

当$a[ i ]==1&&f[i-1]==1/$（$a[i]==0$时可以自己画一下）

假设到a[i+X]之前a[i+?]都是1

&a[i+1]

然后！

&a[i+2]

&a[i+3]

&a[i+4]

&a[i+5]

…

&a[i+X]

a[ i ]

…

! f[i-1]&a [i ]

…

这也就意味着在$f[i+X]$之前$f[i+y]$与$nand[i,i+Y]$一直是相反的，所以他们的区间异或和仅与$X$的奇偶性有关（大家可以自己推一下）。从$i+X$到$R$，$f$数组的结果一直与$nand[i,i+X+…]$相等，这也就意味着这之后的$f$异或和与$nand$相等，所以这部分我们可以用$f$数组的答案来代替$nand$。再考虑前面$f$与$nand$不相等的部分。已经说过这部分异或和仅与$X$的奇偶性有关。

最终答案就是$sum[R]^sum[L-1]^1$（$x$为奇数）$sum[R]^sum[L-1]$（$x$为偶数）。对于查单点要特判$233$然而本蒟蒻并没有特判$233$。

所以询问时暴力处理前几个结果在差分一下$f$数组即可。

$Ctrl+C$完啦

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn=4000010;
 7 inline int read()
 8 {
 9     int x=0,f=1;char c=getchar();
10     while(c<'0'||c>'9')
11     {
12         if(c=='-')f=-f;
13         c=getchar();
14     }
15     while(c>='0'&&c<='9')
16     {
17         x=x*10+c-'0';
18         c=getchar();
19     }
20     return x*f;
21 }
22 int n,m;bool ans,f[maxn],a[maxn],sum[maxn];
23 int haha()
24 {
25     n=read();
26     for(int i=1;i<=n;i++)
27     {
28         int opt,x,y;opt=read();
29         if(opt==1)
30         {
31             x=read()^ans;++m;a[m]=x;
32             if(m==1)f[m]=x;else f[m]=1-(f[m-1]&x);
33             sum[m]=sum[m-1]^f[m];
34         }
35         else 
36         {
37             x=read(),y=read();
38             if(ans)
39             {
40                 x=m-x+1,y=m-y+1;
41                 swap(x,y);
42             }
43             ans=a[x];
44             int j=x;bool s=1-(a[x]&a[x+1]);
45             while(s!=f[j+1]&&j<y)
46             {
47                 ans^=s;
48                 j++;s=1-(s&a[j+1]);
49             }
50             if(j<y)ans^=sum[y]^sum[j];
51             printf("%d
",ans);
52         }
53     }
54 }
55 int sb=haha();
56 int main(){;}