NOIp2018集训test

NOIp2018集训test

szzq学长出的题，先orz一下。

day1

倾斜的线

做过差不多的题，写在我自己的博客里，我却忘得一干二净，反而李巨记得清清楚楚我写了的。

题目就是要最小化这个东西

$|frac{y_i-y_j}{x_i-x_j}- frac{P}{Q}|$

通分

$frac{Q*(y_i-y_j)-P*(x_i-x_j)}{Q*(x_i-x_j)}$

把$Q*x$作为新的$x$,$Q*y-P*x$作为新的$y$,题面转换为求两点斜率绝对值的最小值。

按y排序后可发现答案一定出现在相邻的两点间(画图可得)。

 1 //Achen
 2 #include<bits/stdc++.h>
 3 #define For(i,a,b) for(int i=(a);i<=(b);i++)
 4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
 5 #define Formylove return 0
 6 #define inf 1e18
 7 const int N=2e5+7;
 8 using namespace std;
 9 typedef long long LL;
10 typedef double db;
11 int n,ok;
12 db ans,bs;
13 LL P,Q;
14 
15 template<typename T>void read(T &x) {
16     T f=1; x=0; char ch=getchar();
17     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
18     if(ch=='-') f=-1,ch=getchar();
19     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
20 }
21 
22 struct pt {
23     LL x,y,nx,ny;
24     friend bool operator <(const pt&A,const pt&B) {
25         &;
26     }
27 }p[N],ap,bp;
28 
29 #define eps 1e-15
30 int dcmp(db x) { return fabs(x)<eps?0:(x>0?1:-1); }
31 db xl(pt A,pt B) { return  ((db)A.y-B.y)/(1.0*((db)A.x-B.x)); }
32 LL gcd(LL a,LL b) { 
33     return !b?a:gcd(b,a%b) ; 
34 }
35 
36 #define ANS
37 int main() {
38 #ifdef ANS
39     freopen("slope.in","r",stdin);
40     freopen("slope.out","w",stdout);
41 #endif
42     read(n); read(P); read(Q);
43     For(i,1,n) {
44         read(p[i].x); 
45         read(p[i].y);
46         p[i].nx=Q*p[i].x;
47         p[i].ny=Q*p[i].y-P*p[i].x;
48     }
49     sort(p+1,p+n+1);
50     bs=((db)P)/(1.0*Q);
51     For(i,2,n) {
52         int j=i-1;
53         db t=xl(p[i],p[j]);
54         if(t<0) continue;
55         if(!ok||dcmp(fabs(ans-bs)-fabs(t-bs))>0||(dcmp(fabs(ans-bs)-fabs(t-bs))==0&&dcmp(ans-t)>0)) {
56             ok=1; ans=t; ap=p[i]; bp=p[j];
57         }
58     }
59     if(ap.y<bp.y) swap(ap,bp);
60     LL up=ap.y-bp.y,dn=ap.x-bp.x;
61     LL d=gcd(up,dn);
62     printf("%lld/%lldn",up/d,dn/d);
63     //cerr<<clock()<<endl;
64     Formylove;
65 }

View Code

 

扭动的树

并不难的dp,太久没做dp脑子秀逗了吧。

直接上题解了

二叉查找树按照键值排序的本质是中序遍历,每次我们可以在当前区间中提取出
一个根,然后划分为两个子区间做区间 DP。记 dp[i][j][k]表示区间[i, j]建子树,子树
根节点的父亲是第 k 个数的最大 sum 值之和。由于 k 只能为 i-1 或 j+1,故状态数只
有 O(n^2 ),总复杂度 O(n^3 )。

 1 //Achen
 2 #include<bits/stdc++.h>
 3 #define For(i,a,b) for(int i=(a);i<=(b);i++)
 4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
 5 #define Formylove return 0
 6 const int N=307;
 7 using namespace std;
 8 typedef long long LL;
 9 typedef double db;
10 int n;
11 LL ans=-1,f[N][N][2],sum[N][N],gcd[N][N];
12 
13 template<typename T>void read(T &x) {
14     T f=1; x=0; char ch=getchar();
15     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
16     if(ch=='-') f=-1,ch=getchar();
17     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
18 }
19 
20 struct node {
21     LL k,v;
22     friend bool operator <(const node&A,const node&B) {
23         return A.k<B.k;
24     }
25 }p[N];
26 
27 LL GCD(LL a,LL b) { return !b?a:GCD(b,a%b); }
28 
29 void MX(LL &x,LL y) { if(x<y) x=y; }
30 
31 #define ANS
32 int main() {
33 #ifdef ANS
34     freopen("tree.in","r",stdin);
35     freopen("tree.out","w",stdout);
36 #endif
37     read(n);
38     For(i,1,n) {
39         read(p[i].k);
40         read(p[i].v);
41     }
42     sort(p+1,p+n+1);
43     For(i,1,n) For(j,1,n) gcd[i][j]=GCD(p[i].k,p[j].k);
44     For(i,1,n) For(j,i,n) {
45         sum[i][j]=sum[i][j-1]+p[j].v; 
46     }
47     memset(f,128,sizeof(f));
48     For(i,1,n) {
49         if(i!=1&&gcd[i][i-1]!=1) f[i][i][0]=p[i].v;
50         if(i!=n&&gcd[i][i+1]!=1) f[i][i][1]=p[i].v;    
51     }
52     For(len,2,n) {
53         For(i,1,n-len+1) {
54             int j=i+len-1;
55             if(f[i+1][j][0]>0) {
56                 if(i!=1&&gcd[i-1][i]!=1) 
57                     MX(f[i][j][0],f[i+1][j][0]+sum[i][j]);
58                 if(j!=n&&gcd[j+1][i]!=1)
59                     MX(f[i][j][1],f[i+1][j][0]+sum[i][j]);
60             }
61             if(f[i][j-1][1]>0) {
62                 if(i!=1&&gcd[i-1][j]!=1) 
63                     MX(f[i][j][0],f[i][j-1][1]+sum[i][j]);
64                 if(j!=n&&gcd[j+1][j]!=1) 
65                     MX(f[i][j][1],f[i][j-1][1]+sum[i][j]);
66             }
67             For(k,i+1,j-1) 
68                 if(f[i][k-1][1]>0&&f[k+1][j][0]>0) {
69                     if(i!=1&&gcd[i-1][k]!=1) 
70                         MX(f[i][j][0],f[i][k-1][1]+f[k+1][j][0]+sum[i][j]);
71                     if(j!=n&&gcd[j+1][k]!=1)
72                         MX(f[i][j][1],f[i][k-1][1]+f[k+1][j][0]+sum[i][j]);
73                 }
74         }
75     }
76     if(f[2][n][0]>0) MX(ans,f[2][n][0]+sum[1][n]);
77     if(f[1][n-1][1]>0) MX(ans,f[1][n-1][1]+sum[1][n]);
78     For(i,2,n-1) if(f[1][i-1][1]>0&&f[i+1][n][0]>0) 
79         MX(ans,f[1][i-1][1]+f[i+1][n][0]+sum[1][n]);
80     printf("%lldn",ans);
81     //cerr<<clock()<<endl;
82     Formylove;
83 }

View Code

 

打铁的匠

题目有歧义啊，我以为是每个点到父亲的边权值大于那么多，结果是到指定点的权值大于那么多，，，那么就是线段树合并的裸题了。题解给的treap启发式合并，一个意思。

  1 //Achen
  2 #include<bits/stdc++.h>
  3 #define For(i,a,b) for(int i=(a);i<=(b);i++)
  4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
  5 #define Formylove return 0
  6 const int N=1e5+7;
  7 using namespace std;
  8 typedef long long LL;
  9 typedef double db;
 10 int n,m,UP,fa[N],w[N];
 11 LL ans[N];
 12 
 13 template<typename T>void read(T &x) {
 14     T f=1; x=0; char ch=getchar();
 15     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
 16     if(ch=='-') f=-1,ch=getchar();
 17     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
 18 }
 19 
 20 struct node {
 21     int w,id;
 22     node(int w,int id):w(w),id(id){}
 23 };
 24 vector<node>vc[N];
 25 
 26 LL sg[N*50];
 27 int sg2[N*50];
 28 int ch[N*50][2];
 29 int tot;
 30 #define lc ch[x][0]
 31 #define rc ch[x][1]
 32 #define mid ((l+r)>>1)
 33 int merge(int x,int y,int l,int r) {
 34     if(!(x*y)) return (x^y);
 35     if(l==r) {
 36         sg2[x]+=sg2[y];
 37         sg[x]+=sg[y]; return x;
 38     }
 39     lc=merge(lc,ch[y][0],l,mid);
 40     rc=merge(rc,ch[y][1],mid+1,r);
 41     sg[x]=sg[lc]+sg[rc];
 42     sg2[x]=sg2[lc]+sg2[rc];
 43     return x;
 44 }
 45 
 46 void update(int &x,int l,int r,int pos) {
 47     if(!x) x=++tot;
 48     if(l==r) {
 49         sg[x]+=pos; 
 50         sg2[x]++;
 51         return; 
 52     }
 53     if(pos<=mid) update(lc,l,mid,pos);
 54     else update(rc,mid+1,r,pos);
 55     sg[x]=sg[lc]+sg[rc];
 56     sg2[x]=sg2[lc]+sg2[rc];
 57 }
 58 
 59 #define pr pair<int,LL>
 60 pr operator +(const pr&A,const pr&B) {
 61     return make_pair(A.first+B.first,A.second+B.second);
 62 }
 63 pr qry(int x,int l,int r,int ql,int qr) {
 64     if(!x) return make_pair(0,0);
 65     if(l>=ql&&r<=qr) return make_pair(sg2[x],sg[x]);
 66     if(qr<=mid) return qry(lc,l,mid,ql,qr);
 67     if(ql>mid) return qry(rc,mid+1,r,ql,qr);
 68     return qry(lc,l,mid,ql,qr)+qry(rc,mid+1,r,ql,qr);
 69 }
 70 
 71 int ecnt,fir[N],nxt[N<<1],to[N<<1];
 72 void add(int u,int v) {
 73     nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v;
 74 }
 75 
 76 int rt[N],R[N],sz[N];
 77 int val[N];
 78 void dfs(int x) {
 79     sz[x]=1;
 80     R[x]=R[fa[x]]+1;
 81     for(int i=fir[x];i;i=nxt[i]) {
 82         val[to[i]]=val[x]+w[to[i]];
 83         dfs(to[i]);
 84         sz[x]+=sz[to[i]];
 85     }
 86 }
 87 
 88 void DFS(int x) {
 89     for(int i=fir[x];i;i=nxt[i]) {
 90         DFS(to[i]);
 91         rt[x]=merge(rt[x],rt[to[i]],1,UP);
 92     }
 93     update(rt[x],1,UP,val[x]);
 94     int up=vc[x].size();
 95     For(i,0,up-1) {
 96         int w=vc[x][i].w,id=vc[x][i].id;
 97         pr tt=qry(rt[x],1,UP,val[x]+w,UP);
 98         ans[id]=tt.second-(LL)tt.first*val[x];
 99     }
100 }
101 
102 #define ANS
103 int main() {
104 #ifdef ANS
105     freopen("forging.in","r",stdin);
106     freopen("forging.out","w",stdout);
107 #endif
108     read(n);
109     For(i,2,n) {
110         read(fa[i]);
111         read(w[i]);
112         add(fa[i],i);
113     }
114     read(m);
115     For(i,1,m) {
116         int u,w;
117         read(u); read(w);
118         vc[u].push_back(node(w,i));
119     }
120     UP=(n+1)*1000;
121     dfs(1);
122     DFS(1);
123     For(i,1,m) printf("%lldn",ans[i]);
124     //cerr<<clock()<<endl;
125     Formylove;
126 }
127 /*
128 10
129 1 6
130 2 2
131 3 5
132 2 3
133 5 5
134 6 2
135 5 4
136 10 3
137 1 2
138 4
139 2 3
140 2 2
141 2 5
142 1 3
143 */

View Code

 

day2 

古代龙人的谜题

全机房集体猜题意半小时，终于被辉神凑过了样例。

题目转化求除l,r之外还有1存在，且1的总个数为奇数的区间个数。1的个数为奇数的区间很好找，特判一下只有l,r上有1的区间即可。

 1 //Achen
 2 #include<bits/stdc++.h>
 3 #define For(i,a,b) for(int i=(a);i<=(b);i++)
 4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
 5 #define Formylove return 0
 6 const int N=1e6+7;
 7 using namespace std;
 8 typedef long long LL;
 9 typedef double db;
10 int n,idx;
11 char s[N];
12 
13 template<typename T>void read(T &x) {
14     T f=1; x=0; char ch=getchar();
15     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
16     if(ch=='-') f=-1,ch=getchar();
17     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
18 }
19 
20 #define ANS
21 int main() {
22 #ifdef ANS
23     freopen("puzzle.in","r",stdin);
24     freopen("puzzle.out","w",stdout);
25 #endif
26     read(idx);
27     read(n);
28     scanf("%s",s+1);
29     LL ans=0,c1=0,c0=0;
30     if(s[1]=='0') c0=1; else c1=1;
31     For(i,2,n) {
32         if(s[i]=='1') {
33             ans+=c0;
34             swap(c0,c1);
35             c1++;
36         }
37         else {
38             ans+=c1;
39             c0++;
40         }
41     }
42     int cc=0;
43     For(i,1,n) {
44         if(s[i]=='0') cc++;
45         else {
46             ans-=cc; cc=0;
47         }
48     }
49     cc=0;
50     Rep(i,n,1) {
51         if(s[i]=='0') cc++;
52         else {
53             ans-=cc; cc=0;
54         }
55     }
56     printf("%lldn",ans);
57     //cerr<<clock()<<endl;
58     Formylove;
59 }

View Code

 

交错的字符串

这个就是传说中的折半搜索？

把字符串拆成{S1,S2},即n个字符属于S1,n个属于S2，那么根据前n个字符哪些属于S1哪些属于S2就可以得出S1，S2是什么串了。

暴力枚举前n个哪些属于S1，用mp存下这种情况对应的串，再暴力枚举后n个位置能对应的串计算答案即可。

 1 //Achen
 2 #include<bits/stdc++.h>
 3 #define For(i,a,b) for(int i=(a);i<=(b);i++)
 4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
 5 #define Formylove return 0
 6 const int N=40;
 7 using namespace std;
 8 typedef long long LL;
 9 typedef double db;
10 int n;
11 LL ans;
12 char s[N],a[N];
13 
14 template<typename T>void read(T &x) {
15     T f=1; x=0; char ch=getchar();
16     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
17     if(ch=='-') f=-1,ch=getchar();
18     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
19 }
20 
21 #define pr pair<LL,LL>
22 #define MP make_pair
23 #define fi first
24 #define se second
25 map<pr,int>mp[20];
26 
27 pr hash() {
28     pr rs=MP(0,0);
29     For(i,1,n/2) 
30         rs.fi=rs.fi*10+a[i]-'a';
31     For(i,n/2+1,n) 
32         rs.se=rs.se*10+a[i]-'a';
33     return rs;
34 }
35 
36 #define ANS
37 int main() {
38 #ifdef ANS
39     freopen("string.in","r",stdin);
40     freopen("string.out","w",stdout);
41 #endif
42     read(n);
43     scanf("%s",s+1);
44     int up=(1<<n)-1;
45     For(S,0,up) {
46         int cc=0,l=1,r=n;
47         For(i,1,n) {
48             if(S&(1<<(i-1))) { cc++; a[l++]=s[i]; }
49             else a[r--]=s[i];
50         }
51         pr H=hash();
52         mp[cc][H]++;
53     }
54     For(S,0,up) {
55         int cc=0,l=1,r=n;
56         For(i,1,n) {
57             if(S&(1<<(i-1))) { cc++; a[l++]=s[2*n-i+1]; } 
58             else a[r--]=s[2*n-i+1];
59         }
60         pr H=hash();
61         if(mp[cc][H]) 
62             ans+=mp[cc][H];
63     }
64     printf("%lldn",ans/2);
65     //cerr<<clock()<<endl;
66     Formylove;
67 }

View Code

 

世界第一的猛汉王

以为能AK结果把曼哈顿距离误当成切比雪夫距离然后爆0了。

把x,y改成x+y,x-y就A了？？？

亏死了。

题解：

先把曼哈顿距离转换成切比雪夫距离，然后距离一个点距离不超过d的范围变成了一个框框，非常优美。

题目转换为给定一张竞赛图，有些边未定向，给这些边定向使得猛汉三角最多和最少。

点分为黑白两色，根据题目要求，猛汉三角只能是黑白黑或者白黑白，考虑一种情况，另一种是对称的。

猛汉三角只能长这样

对于一个黑点，一个在它框内的白点a和不在它框内的白点b，如果a,b之间的边是b指向a的，贡献就为1。

也就是对于两个白点a,b，如果边是b指向a的，那么贡献就是在a的框内不在b的框内的黑点个数，反之亦然。

那么最大的答案就是，考虑每一对同色点，在其中一个的框内不在另一个框内的点的个数较多的个数之和，最小反之。

发现比较每一对同色的点的这个（”在其中一个的框内不在另一个框内的点的个数“）个数，公共的部分没有影响，也就是比较这对点的框内的异色点的个数。那么按框内异色点的个数排序，答案最大的时候我和我前面的点都选我，我和我后面的点都选我后面的，最小反之。

求每个点框内异色点的个数，扫描线即可，闲的蛋疼的话估计啥子树套树也不是不能做。

 

  1 //Achen
  2 #include<bits/stdc++.h>
  3 #define For(i,a,b) for(int i=(a);i<=(b);i++)
  4 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
  5 #define Formylove return 0
  6 const int N=1e5+7;
  7 using namespace std;
  8 typedef long long LL;
  9 typedef double db;
 10 int n,m,d;
 11 LL UP=3e9+1;
 12 LL ans1,ans2;
 13 
 14 template<typename T>void read(T &x) {
 15     T f=1; x=0; char ch=getchar();
 16     while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
 17     if(ch=='-') f=-1,ch=getchar();
 18     for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
 19 }
 20 
 21 int rt,tot,sg[N*50],ch[N*50][2];
 22 #define lc ch[x][0]
 23 #define rc ch[x][1]
 24 #define mid ((l+r)>>1)
 25 void update(int &x,LL l,LL r,LL pos) {
 26     if(!x) {
 27         x=++tot; sg[x]=lc=rc=0;
 28     }
 29     if(l==r) {
 30         sg[x]++; return;
 31     }
 32     if(pos<=mid) update(lc,l,mid,pos);
 33     else update(rc,mid+1,r,pos);
 34     sg[x]=sg[lc]+sg[rc];
 35 }
 36 
 37 int qry(int x,LL l,LL r,LL ql,LL qr) {
 38     if(!x) return 0;
 39     if(l>=ql&&r<=qr) return sg[x];
 40     if(qr<=mid) return qry(lc,l,mid,ql,qr);
 41     if(ql>mid) return qry(rc,mid+1,r,ql,qr);
 42     return qry(lc,l,mid,ql,qr)+qry(rc,mid+1,r,ql,qr);
 43 }
 44 
 45 struct node {
 46     LL x,y,k;
 47     friend bool operator <(const node&A,const node&B) {
 48         return A.k<B.k;
 49     }
 50 }b[N],w[N];
 51 
 52 struct Q{
 53     LL x,l,r; int f,id;
 54     Q(){}
 55     Q(LL x,LL l,LL r,int f,int id):x(x),l(l),r(r),f(f),id(id){}
 56     friend bool operator<(const Q&A,const Q&B) {
 57         return A.x&(A.x==B.x&&A.f<B.f);
 58     }
 59 }q[N*10];
 60 int cnt;
 61 
 62 void solve(node b[],node w[],int n,int m) {
 63     rt=tot=0; cnt=0;
 64     For(i,1,n) 
 65         q[++cnt]=Q(b[i].x,b[i].y,b[i].y,0,i);
 66     For(i,1,m) {
 67         if(w[i].x-d>1) q[++cnt]=Q(w[i].x-d-1,max(w[i].y-d,1LL),min(w[i].y+d,UP),1,i);
 68         q[++cnt]=Q(min(w[i].x+d,UP),max(w[i].y-d,1LL),min(w[i].y+d,UP),2,i);
 69     }
 70     sort(q+1,q+cnt+1);
 71     For(i,1,cnt) {
 72         if(q[i].f==0) update(rt,1,UP,q[i].l);
 73         else {
 74             int tp=qry(rt,1,UP,q[i].l,q[i].r);
 75             if(q[i].f==1) w[q[i].id].k-=tp;
 76             else w[q[i].id].k+=tp;
 77         }
 78     }
 79 }
 80 
 81 #define ANS
 82 int main() {
 83 #ifdef ANS
 84     freopen("mhw.in","r",stdin);
 85     freopen("mhw.out","w",stdout);
 86 #endif
 87     read(n); read(m); read(d);
 88     For(i,1,n) {
 89         LL x,y;
 90         read(x); read(y);
 91         b[i].x=x+y+1e9+1;
 92         b[i].y=x-y+1e9+1;
 93     }
 94     For(i,1,m) {
 95         LL x,y;
 96         read(x); read(y);
 97         w[i].x=x+y+1e9+1;
 98         w[i].y=x-y+1e9+1;
 99     }
100     solve(b,w,n,m);
101     solve(w,b,m,n);
102     For(i,1,n) {
103         LL tp=b[i].k;
104         ans1-=tp*(tp-1)/2;
105         ans2-=tp*(tp-1)/2;
106     }
107     For(i,1,m) {
108         LL tp=w[i].k;
109         ans1-=tp*(tp-1)/2;
110         ans2-=tp*(tp-1)/2;
111     }
112     sort(b+1,b+n+1);
113     sort(w+1,w+m+1);
114     For(i,1,n) {
115         ans1+=b[i].k*(n-i);
116         ans2+=b[i].k*(i-1);
117     }
118     For(i,1,m) {
119         ans1+=w[i].k*(m-i);
120         ans2+=w[i].k*(i-1);
121     }
122     printf("%lld %lldn",ans1,ans2);
123     //cerr<<clock()<<endl;
124     Formylove;
125 }

View Code

 

转载于:.html