![[hgoi#2019/2/24]玄学考试](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "[hgoi#2019/2/24]玄学考试")
感想
对于这次考试，真的不想说什么了，太玄学了！！！
t1输出比标准输出长，这是什么操作？？？难道要关文件？？？但是交到oj上又A掉了。这是什么操作。
t2还好，没有出什么意外。。。但是要吐槽一下出题人，为什么空间给这么小！！！
t3的正解竟然是随机乱搞？？？
t4竟然给我玄学错掉了一个点，交到oj上还都是对的？？？
以上吐槽完毕
t1 密码(password)
题目大意
求出 \(\sum_{i=1}^{n} i^2 2^i\) 。
题解
遇到这种有倍数关系的累加和，一般都可以用错位相减法。
\[ Sn=1 \times 2^1 + 4 \times 2^2 + \cdots + n^2 \times 2^n \]
\[ 2 \times Sn=1 \times 2^2 + 4 \times 2^3 +\cdots + n^2 \times 2^{n+1} \]
上下两式错位相减得到以下算式
\[ Sn = n^2 \times 2^{n+1}-(1 \times 2^1 + 3 \times 2^2 + \cdots + ( 2 \times n -1) \times 2^n )\]
我们接下来的任务就是把后面那个玩意化简掉，依旧是用错位相减法
\[ Tn = 1 \times 2^1 + 3 \times 2^2 + \cdots + ( 2 \times n -1) \times 2^n \]
\[ 2 \times Tn = 1 \times 2^2 + 3 \times 2^3 + \cdots + ( 2 \times n -1) \times 2^{n+1} \]
上下两式错位相减得到以下算式
\[ Tn=(2\times n-1) \times 2^{n+1} - ( 2 + 2^3 + 2^4 + \cdots + 2^{n+1} )\]
\[ Tn=(2\times n-1) \times 2^{n+1} - (2 + 2^2 + 2^3 + \cdots + 2^{n+1} ) + 2^2 \]
\[ Tn=(2\times n-1) \times 2^{n+1} - ( 2^{n+2} - 2 ) + 2^2 \]
\[ Tn=(2\times n-1) \times 2^{n+1} - 2 \times 2^{n+1} + 6 \]
\[ Tn=(2\times n-3) \times 2^{n+1} + 6 \]
那么将式子代回去，就可以得到：
\[ Sn=n^2\times 2^{n+1} - (2\times n-3) \times 2^{n+1} - 6 \]
\[ Sn=(n^2-2\times n + 3) \times 2^{n+1} - 6 \]
ac代码
#include<bits/stdc++.h>
#define mod 1000000007
#define LL long long
using namespace std;
LL n;
LL power(LL n,LL m){
LL res=1;
while(m!=0){
if(m&1) res=(res*n)%mod;
n=(n*n)%mod;
m>>=1;
}
return res;
}
int main(){
scanf("%lld",&n);
LL ans=(n*n)%mod;
ans=(ans-2*n+3+mod)%mod;
LL tmp=power(2,n+1);
ans=((ans*tmp)%mod-6+mod)%mod;
printf("%lld\n",ans);
return 0;
}t2 卡内存(memory)
题目大意
三种操作：
- 单点修改
- 查询区间和
- 回归到某此操作后的状态
解法
查询历史状态？？？这不就是主席树模板吗？（快速掏出了一个主席树模板，正准备往上面改）
但是给的空间只有\(8mb\)，用主席树来做至少也要把所有的数组都开小10倍，那么不是MLE就是WA或者是RE。
那么怎么做呢？因为没有查询历史的信息，而只是回归到历史的状态，我们可以想到非常像递归搜索dfs的做法，我们也这样想一下。
我们将这些询问建成一个图，如果要回归，那么就将当前这个连到回归的节点上。
那么最后离线跑一遍dfs就可以了，在离线用线段树或者是树状数组存储一下就好了。
ac代码
#include<bits/stdc++.h>
#define lowbit(x) x&-x
#define N 100005
using namespace std;
struct edge{
int to,nt;
}E[N];
struct node{
int id,x,y,ans;
}q[N];
int cnt,n,m;
int H[N],c[N];
int read(){
int w=0,x=0;char ch=0;
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return w?-x:x;
}
void addedge(int u,int v){
E[++cnt]=(edge){v,H[u]}; H[u]=cnt;
}
void add(int x,int v){
while(x<=n) c[x]+=v,x+=lowbit(x);
}
int query(int x){
int ret=0;
while(x>0) ret+=c[x],x-=lowbit(x);
return ret;
}
void dfs(int u){
if(q[u].id==1) add(q[u].x,q[u].y);
else if(q[u].id==2) q[u].ans=query(q[u].y)-query(q[u].x-1);
for(int e=H[u];e;e=E[e].nt){
int v=E[e].to;
dfs(v);
}
if(q[u].id==1) add(q[u].x,-q[u].y);
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++) add(i,read());
for(int i=1;i<=m;i++){
char opt[20];
scanf("%s",opt);
if(opt[1]=='d'){
int x=read(),y=read();
q[i]=(node){1,x,y,0};
addedge(i-1,i);
}
else if(opt[1]=='s'){
int x=read(),y=read();
q[i]=(node){2,x,y,0};
addedge(i-1,i);
}
else{
int x=read();
q[i]=(node){3,x,0,0};
addedge(x,i);
}
}
dfs(0);
for(int i=1;i<=m;i++) if(q[i].id==2) printf("%d\n",q[i].ans);
return 0;
}t3 图像分析(graph)
题目大意
求出一条直线，这条直线经过平面内的\(\frac{1}{3}\)个点。
解法
解法真的玄，如果小于300就暴力{n^3}枚举。
如果大于300，那么就随机找两个点，看看是不是符合我们的题意。
好像这样做正确率是\(\frac{8}{9}^100\)，不是非酋都能过。
ac代码
#include<bits/stdc++.h>
#define LL long long
#define N 900005
using namespace std;
struct node{
LL x,y;
}a[N];
int n;
void solve1(){
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
int sum=2;
for(int k=1;k<=n;k++){
if(i==k||k==j) continue;
if(((a[i].y-a[j].y)*(a[k].x-a[i].x))==((a[i].x-a[j].x)*(a[k].y-a[i].y)))sum++;
if(sum*3>=n){
printf("%d %d\n",i,j);
return;
}
}
}
}
}
void solve2(){
while(1){
int i=(1ll*(rand()%n+1)*(rand()%n+1))%n+1,j=(1ll*(rand()%n+1)*(rand()%n+1))%n+1;
if(i<j) swap(i,j);
while(i==j)j=(1ll*(rand()%n+1)*(rand()%n+1))%n+1;
int sum=2;
for(int k=1;k<=n;k++){
if(i==k||k==j) continue;
if(((a[i].y-a[j].y)*(a[k].x-a[i].x))==((a[i].x-a[j].x)*(a[k].y-a[i].y)))sum++;
if(sum*3>=n){
printf("%d %d\n",i,j);
exit(0);
}
}
}
}
int main(){
srand(time(NULL));
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].x,&a[i].y);
if(n<=300) solve1();
else solve2();
return 0;
}
t4 JYM 的公司(volume)
题目大意
输出一个数列中两两差的绝对值的和。
解法
比较简单。
我们从小到大排序，计算每个相差对答案有多少的贡献。
因为每一次的增加都会对后面的答案多增加一些贡献，那么我们就一边遍历一边累加贡献。
ac代码
#include<bits/stdc++.h>
#define LL long long
#define N 500000
using namespace std;
int n;
LL a[N],t[N],sum[N],ans=0,S[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
sort(a+1,a+1+n);
LL res=0;
for(int i=2;i<=n;i++){
res+=(i-1)*(a[i]-a[i-1]);
ans+=res;
}
printf("%lld\n",ans*2);
return 0;
}