首页 > 代码库 > 8.8联考题解
8.8联考题解
今天的T1让我怀疑我是不是在做奥赛题……这考的是什么知识点啊这个，会不会用绝对值函数？
Evensgn 的债务
时间限制: 1 Sec 内存限制: 128 MB
题目描述
Evensgn 有一群好朋友，他们经常互相借钱。假如说有三个好朋友A，B，C。A 欠 B 20 元，B 欠 C 20 元，总债务规模为 20+20=40 元。Evensgn 是个追求简约的人，他觉得这样的债务太繁杂了。他认为，上面的债务可以完全等价为 A 欠C20 元，B 既不欠别人，别人也不欠他。这样总债务规模就压缩到了 20 元。现在给定 n 个人和 m 条债务关系。Evensgn 想找到一种新的债务方案，使得每个人欠钱的总数不变，或被欠钱的总数不变（但是对象可以发生变化），并且使得总债务规模最小。
输入
输入文件第一行两个数字 n; m，含义如题目所述。
接下来 m 行，每行三个数字 ai; bi; ci，表示 ai 欠 bi 的钱数为 ci。
注意，数据中关于某两个人 A 和 B 的债务信息可能出现多次，将其累加即可。
如”A 欠 B 20 元”、”A 欠 B 30 元”、”B 欠 A 10 元”，其等价为”A 欠 B 40 元”。
输出
输出文件共一行，输出最小的总债务规模。
样例输入输出
样例输入 1 5 3 1 2 10 2 3 1 2 4 1 样例输入 2 4 3 1 2 1 2 3 1 3 1 1
样例输出
样例输出 1 10 样例输出 2 0
数据范围
对于 30% 的数据，1 ≤ n ≤ 10，1 ≤ m ≤ 10。
对于 60% 的数据，1 ≤ n ≤ 100, 1 ≤ m ≤ 104。
对于 80% 的数据，1 ≤ n ≤ 104，1 ≤ m ≤ 104。
对于 100% 的数据，1 ≤ n ≤ 106，1 ≤ m ≤ 106。
对于所有的数据，保证 1 ≤ ai; bi ≤ n; 0 < ci ≤ 100。
题解
不想写题解……刚开始觉得，这是绝对值之和/2吧？弄了个环的例子绕一绕，好像还真没什么问题……后来闲得慌自己证明，发现用负数表示borrow，正数表示lend，正负数一消取绝对值正好是债务规模，似乎挺有道理？交题之前又有些犹豫，这题是考的什么算法啊？还是交了，居然A了……A掉这道题，你需要掌握：循环语句、开数组、输入输出、调库、绝对值函数(不会用cmath库用if语句判断取相反数也行)，可以给下一届高一当第一次考试题了；或许文化课一调的语句填空也行。昨天的第一题，虽然是原题好歹是题，还用了MP算法，但是这个，完全不懂意义何在。
include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; const int sj=1000010; int a[sj]={0},n,m,a1,a2,a3,ans=0; int r() { int jg=0,jk; jk=getchar()-‘0‘; if(jk<=9&&jk>0) jg=jk; jk=getchar()-‘0‘; while(jk>=0&&jk<=9) { jg=jg*10+jk; jk=getchar()-‘0‘; } return jg; } int main() { //freopen("t1.txt","r",stdin); n=r(); m=r(); for(int i=1;i<=m;i++) { a1=r(); a2=r(); a3=r(); a[a1]-=a3; a[a2]+=a3; } for(int i=1;i<=n;i++) ans+=abs(a[i]); ans/=2; printf("%d",ans); //while(1); return 0; }
Number
时间限制: 1 Sec 内存限制: 256 MB
题目描述
一个排列，求出了 a 数组，其中 ai 表示第 i 个数左边有多少个数比它小
计算出原来的排列
输入
第一行输入 n 接下来 n - 1 个整数 ai，下标从 2 开始
输出
输出 n 个整数表示原排列
样例输入
5
1
2
1
0
样例输出
2
4
5
3
1
提示
对于 20% 的数据满足：1 ≤ n ≤ 10
对于 50% 的数据满足：1 ≤ n ≤ 1000
对于 100% 的数据满足，1 ≤ n ≤ 100000
保证解存在
题解
这道题还是比较有意思的。刚开始啥都想不出来，先打了个dfs，又弄了个出数据的程序(走向对拍？)。发现dfs只能跑20分，有点难过。第三题看起来很不友好，第二题还拿不了分这是要完啊……然后写写画画，猛然发现这个最后一个好像是确定的，那倒数第二个呢，倒数第三个呢……这不就想出来了吗，记录一下每个数的temp(左边可能有几个比它小的)，选出来一个就把比它大的都--，每次查哪一个数正好符合要求就行了。需要快速查询，一开始想的是链表。打了个(n^2+2^n)/2的链表版本，出不了样例，又转去打n^2的，发现好像先选大的和先选小的还不一样。感性地论证一下，较小数的temp更不容易变小，所以尽量先选小的。心怀疑虑地把链表版本改对，和1000的数据拍了一下发现能过，也就放心了。其实这个效率跑个10000也是绰绰有余的，但是出题人说给50就给50多一点分都没有QAQ。第三题想不出来再回来看，要把n^2降下来，查询得放在树上，恍然大悟——原来是个平衡树题啊。但是没想到可以用有旋Treap查询和删除，被50分版本限制住了思路一直想着Splay或者无旋Treap的区间操作，Splay极容易打挂无旋Treap没打过区间build函数不会写，还是算了(早知道有旋Treap也可以做就打正解了嘛)。下午改题欢乐地拿有旋Treap轻松水过，delete函数写错一个字母又查了半天错。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; const int sj=100010; int n,a[sj],ans[sj],size,root; struct Treap { int v,l,r,key,size; }t[sj]; void update(int x) { t[x].size=t[t[x].l].size+t[t[x].r].size+1; } void rturn(int &x) { int tt=t[x].l; t[x].l=t[tt].r; t[tt].r=x; t[tt].size=t[x].size; update(x); x=tt; } void lturn(int &x) { int tt=t[x].r; t[x].r=t[tt].l; t[tt].l=x; t[tt].size=t[x].size; update(x); x=tt; } void cr(int &x,int y) { if(x==0) { size++; x=size; t[x].size=1; t[x].v=y; t[x].key=rand(); return; } t[x].size++; if(y>t[x].v) { cr(t[x].r,y); if(t[t[x].r].key<t[x].key) lturn(x); } else { cr(t[x].l,y); if(t[t[x].l].key<t[x].key) rturn(x); } } int query(int x,int y) { if(x==0) return 0; if(t[t[x].l].size>=y) return query(t[x].l,y); if(t[t[x].l].size+1<y) return query(t[x].r,y-t[t[x].l].size-1); return t[x].v; } void sc(int &x,int y) { if(x==0) return; if(t[x].v==y) { if(t[x].l*t[x].r==0) x=t[x].l+t[x].r; else if(t[t[x].l].key<t[t[x].r].key) rturn(x),sc(x,y); else lturn(x),sc(x,y); } else if(y>t[x].v) t[x].size--,sc(t[x].r,y); else t[x].size--,sc(t[x].l,y); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) cr(root,i); for(int i=2;i<=n;i++) scanf("%d",&a[i]); ans[n]=a[n]+1; sc(root,ans[n]); for(int i=n-1;i>1;i--) { ans[i]=query(root,a[i]+1); sc(root,ans[i]); } ans[1]=t[root].v; for(int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0; }
与非
时间限制: 2 Sec 内存限制: 256 MB
题目描述
作为一名新世纪共产主义的接班人，你认识到了资本主义的软弱性与妥协性，决定全面根除资本主义，跑步迈入共产主义。但是当你即将跨入共产主义大门的时候，遇到了万恶的资本家留下的与非电路封印，经过千辛万苦的研究，你终于把复杂的破解转变成了以下问题：
初始时你有一个空序列，之后有N个操作。
操作分为一下两种：
1 x：在序列末尾插入一个元素x(x=0或1)。
2 L R：定义nand[L,R]为序列第L个元素到第R个元素的与非和，询问nand[L,L]^nand[L,L+1]^nand[L,L+2]^......^nand[L,R]。
Nand就是先与，再取反
输入
从文件nand.in中读入数据。
输入第一行一个正整数N，表示操作个数。
接下来N行表示N个操作。
为了体现程序的在线性，记lastans为上一次操作二的回答，初始lastans=0,。对于操作1，你需要对x异或lastans。对于操作二，设现在序列中的元素个数为M，如果lastans=1，那么你需要作如下操作：L=M-L+1,R=M-R+1,swap(L,R)
输出
输出到nand.out中。
输出有多行。为对于每一个操作二的回答。
样例输入
6
1 1
1 1
1 0
2 1 2
2 1 3
2 2 3
样例输出
1
0
0
提示
【数据规模和约定】
数据点 N的规模 操作一的个数M1 操作二的个数M2
1 N<=1000 M1<=500 M2<=500
2 N<=1000 M1<=500 M2<=500
3 N<=200000 M1<=100000 M2<=100000
4 N<=200000 M1<=100000 M2<=100000
5 N<=1000000 M1<=900000 M2<=100000
6 N<=4000000 M1<=3900000 M2<=100000
7 N<=4000000 M1<=3900000 M2<=100000
8 N<=4000000 M1<=3900000 M2<=100000
9 N<=4000000 M1<=3900000 M2<=100000
10 N<=4000000 M1<=3900000 M2<=100000
对于所有数据，满足N<=4000000,M1<=3900000,M2<=100000,x={0,1},L<=R。
由于输入规模较大，请使用较快的读入方式以防读入超时。
题解
%%%超哥。我承认我确实没读懂题，所以连20的暴力分都没拿到。连续两天T3爆零，很忧伤啊。超哥的思路完胜std！
f[i]=!(f[i-1]&a[i])
nand[i,j]=!(nand[i,j-1]&a[j])=!(……!(!(!(a[i]&a[i+1]))&a[i+2])……&a[j])
f[j]=!(f[j-1]&a[j])=!(……!(!(!(f[i-1]&a[i])&a[i+1]))&a[i+2])……&a[j])
唯一的差别在中间部分，真正的nand[i,j]是a[i]&a[i+1],而f[j]是(!(f[i-1]&a[i]))&a[i+1]
a[i+1]=0时前后都是0，一定相等
a[i+1]=1时若a[i]=0,前为0，后为1
若a[i]=1且f[i-1]=1，前为1，后为0
若a[i]=1但f[i-1]=0,前后还是相等的
对于每一个询问的区间，从它有一位为0开始就可以套根据f数组计算出的前缀和sum了~至于前面的，暴力算吧。
其实也是想了想前缀和区间转化之类的思路的，但是没想出来……改题的时候想着亦或有可减性(亦或两次变成1)，本蒟蒻傻傻地打了sum[r]-sum[l-1]然后成功出了负数……最后批判这个题面一句：名字叫与非，题干里说先与再取反，虽然说大概能理解可是毕竟二进制还有个~运算叫取反啊……
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int sj=3900005; int r() { int jg=0,jk; jk=getchar()-‘0‘; if(jk<=9&&jk>0) jg=jk; jk=getchar()-‘0‘; while(jk>=0&&jk<=9) { jg=jg*10+jk; jk=getchar()-‘0‘; } return jg; } int n,a1,a2,op,s[sj],lans,ge,t,jg,f[sj],sum[sj],na[sj]; int main() { n=r(); sum[0]=1; for(int l=1;l<=n;l++) { op=r(); a1=r(); if(op==1) { a1^=lans; ge++; s[ge]=a1; f[ge]=!(f[ge-1]&s[ge]); sum[ge]=sum[ge-1]^f[ge]; if(ge==1) f[1]=s[1],sum[1]=s[1]; } if(op==2) { a2=r(); if(lans==1) { a1=ge-a1+1; a2=ge-a2+1; t=a1; a1=a2; a2=t; } jg=na[a1]=s[a1]; for(int j=a1+1;j<=a2;j++) { if(s[j]==1) { na[j]=!(na[j-1]&s[j]); jg^=na[j]; } else { jg^=sum[a2]; jg^=sum[j-1]; break; } } lans=jg; printf("%d\n",jg); } } return 0; }
8.8联考题解