NOIP2018复赛提高组C++复赛标程+数据

第二十四届全国青少年信息学奥林匹克联赛复赛——提高组C++语言试题

A.道路铺设

标程

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define Hzy(o) freopen(o".in", "r", stdin), freopen(o".out", "w", stdout)

using namespace std;

const int N = 100010;

struct Node {

int val, pos;

bool operator < (const Node & p) const { return val < p.val; }

}a[N];

bool vis[N];

int n, ans;

int main() {

Hzy("road");

scanf("%d", &n);

for(int i = 1; i <= n; ++i) {

scanf("%d", &a[i].val);

a[i].pos = i;

}

sort(a + 1, a + n + 1);

int cnt = 0, t1, t2;

for(int i = n; i >= 1; --i) {

t1 = a[i].pos - 1;

t2 = a[i].pos + 1;

vis[a[i].pos] = 1;

cnt++;

if(t1 > 0 && t1 <= n && vis[t1]) cnt--;

if(t2 > 0 && t2 <= n && vis[t2]) cnt--;

ans += (a[i].val - a[i - 1].val) * cnt;

}

cout << ans << endl;

return 0;

}

B.货币系统

标程

#include <iostream>

#include <cmath>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

const int N=600,M=51000;

int f[M],n,m,a[N];

void solve(){

scanf("%d",&n);

for (int i=1;i<=n;i++) scanf("%d",&a[i]);

sort(a+1,a+n+1); m=0;

for (int i=1;i<=n;i++) m=max(m,a[i]);

memset(f,0x00,sizeof f); f[0]=1; int ans=0;

for (int i=1;i<=n;i++){

if (f[a[i]]) continue; ans++;

for (int j=a[i];j<=m;j++) f[j]|=f[j-a[i]];

}

printf("%d\n",ans);

}

int main(){

int t; scanf("%d",&t);

for (;t;t--) solve();

return 0;

}

C.赛道修建

标程一

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<ctime>

const int maxn=100010;

int n,m;

struct edge{int to,len;edge*next;}E[maxn*2],*ne=E,*fir[maxn];

void link(int u,int v,int l){*ne=(edge){v,l,fir[u]};fir[u]=ne++;}

int f[maxn],g[maxn],l[maxn];

int chk(int M,int c,int d){

int s=0;

for(int i=c,j=-1;--i>j;)if(i!=d){

if(l[i]>=M)s++;

else{

while(++j<i&&(j==d||l[j]+l[i]<M));

if(j<i)s++;

}

}

return s;

}

int b[maxn];

int dfs(int M,int i,int fa){

f[i]=0;

for(edge*e=fir[i];e;e=e->next)if(e->to!=fa){

dfs(M,e->to,i);

f[i]+=f[e->to];

}

int c=0;

for(edge*e=fir[i];e;e=e->next)if(e->to!=fa)

l[c++]=g[e->to]+e->len;

std::sort(l,l+c);

int s=chk(M,c,-1),left=-1,right=c,mid;

while(right-left>1)chk(M,c,mid=left+right>>1)<s?right=mid:left=mid;

f[i]+=s;

g[i]=left<0?0:l[left];

return f[i];

}

int main(){

scanf("%d%d",&n,&m);

int left=0,right=1,mid;

for(int i=1,u,v,l;i<n;i++)scanf("%d%d%d",&u,&v,&l),link(u,v,l),link(v,u,l),right+=l;

//fprintf(stderr,"%lfs\n",clock()/(double)CLOCKS_PER_SEC);

while(right-left>1)dfs(mid=left+right>>1,1,0)>=m?left=mid:right=mid;

printf("%d\n",left);

//fprintf(stderr,"%lfs\n",clock()/(double)CLOCKS_PER_SEC);

}

标程二

#include<cstdio>

#include<algorithm>

#include<ctime>

#include<cstring>

const int maxn=100010;

int n,m;

struct edge{int to,len;edge*next;}E[maxn*2],*ne=E,*fir[maxn];

void link(int u,int v,int l){*ne=(edge){v,l,fir[u]};fir[u]=ne++;}

int f[maxn],g[maxn],l[maxn];

int b[maxn],bl[maxn*2];

void rsort(int*a,int n){

int d=0;while((1<<d)<n)d++;

for(int i=0;i<30;i+=d){

memset(bl,0,sizeof(*bl)<<d);

for(int j=0;j<n;j++)bl[(a[j]>>i&(1<<d)-1)+1]++;

for(int j=0;j<1<<d;j++)bl[j+1]+=bl[j];

for(int j=0;j<n;j++)b[bl[a[j]>>i&(1<<d)-1]++]=a[j];

memcpy(a,b,sizeof(*a)*n);

}

}

int dfs(int M,int v,int fa){

f[v]=0;

for(edge*e=fir[v];e;e=e->next)if(e->to!=fa){

dfs(M,e->to,v);

f[v]+=f[e->to];

}

int c=0;

for(edge*e=fir[v];e;e=e->next)if(e->to!=fa)

l[c++]=g[e->to]+e->len;

if(c<64)std::sort(l,l+c);

else rsort(l,c);

int s=0,t=0,la=c;

for(int i=c,j=-1;--i>j;s++){

if(l[i]>=M)la=i;

else{

while(++j<i&&l[i]+l[j]<M)t=l[j];

if(j==i){t=l[la-1];break;}

if(i&&l[i-1]+l[j]<M)la=i;

}

}

f[v]+=s;g[v]=t;

return f[v];

}

int main(){

scanf("%d%d",&n,&m);

int left=0,right=1,mid;

for(int i=1,u,v,l;i<n;i++)scanf("%d%d%d",&u,&v,&l),link(u,v,l),link(v,u,l),right+=l;

//fprintf(stderr,"%lfs\n",clock()/(double)CLOCKS_PER_SEC);

while(right-left>1)dfs(mid=left+right>>1,1,0)>=m?left=mid:right=mid;

printf("%d\n",left);

//fprintf(stderr,"%lfs\n",clock()/(double)CLOCKS_PER_SEC);

}

D.旅行

标程

#include <stdio.h>

#include <algorithm>

const int MAXN = 300005;

int n, m;

struct edge {

int u, v, id;

};

bool operator < (const edge &a, const edge &b) {

return a.u < b.u || (a.u == b.u && a.v < b.v);

}

edge edges[MAXN * 2];

edge *first[MAXN];

int stack[MAXN];

int stack_eid[MAXN];

bool instack[MAXN];

int top;

bool found;

bool is_on_cycle[MAXN];

void dfs(int u, int last) {

stack[++top] = u;

instack[u] = true;

for (edge *e = first[u]; e->u == u; e++) {

int v = e->v;

if (v == last) continue;

if (instack[v]) {

found = true;

is_on_cycle[e->id] = true;

while (stack[top] != v) {

is_on_cycle[stack_eid[top - 1]] = true;

--top;

}

return;

}

stack_eid[top] = e->id;

dfs(v, u);

if (found) return;

}

instack[u] = false;

--top;

}

int ans_idx;

bool visit[MAXN];

bool del;

void dfs(int u) {

printf("%d%c", u, " \n"[++ans_idx == n]);

visit[u] = true;

++top;

bool done = false;

for (edge *e = first[u]; e->u == u; e++) {

int v = e->v;

if (visit[v]) continue;

edge *e1 = e + 1;

while (e1->u == u && visit[e1->v]) ++e1;

if (e1->u == u) {

stack[top] = e1->v;

} else {

--top;

done = true;

}

if (!del && is_on_cycle[e->id] && v > stack[top]) {

del = true;

} else {

dfs(v);

}

}

if (!done) --top;

}

int main() {

scanf("%d%d", &n, &m);

if (n == 1) {

return puts("1"), 0;

}

for (int i = 0; i < m; i++) {

int u, v;

scanf("%d%d", &u, &v);

edges[i * 2] = (edge){u, v, i};

edges[i * 2 + 1] = (edge){v, u, i};

}

std::sort(edges, edges + 2 * m);

first[1] = edges;

for (int i = 1; i < 2 * m; i++) {

if (edges[i].u != edges[i - 1].u) {

first[edges[i].u] = edges + i;

}

}

dfs(1, 0);

top = 0;

stack[0] = n + 1;

dfs(1);

}

标程二

#include <stdio.h>

#include <string.h>

#include <algorithm>

const int MAXN = 300005;

int n, m;

struct data {

int u, v, id;

};

bool operator < (const data &a, const data &b) {

return a.u < b.u || (a.u == b.u && a.v < b.v);

}

data _edges[MAXN * 2];

data *first[MAXN];

int ans[MAXN];

int dfsseq[MAXN];

int visit[MAXN];

int del_e;

int dfs_idx;

bool ok;

bool fail;

#define visit_id (del_e + 1)

void dfs(int x) {

if (!ok) {

if (x < ans[dfs_idx]) {

ok = true;

} else if (x > ans[dfs_idx]) {

fail = true;

return;

}

}

dfsseq[dfs_idx++] = x;

visit[x] = visit_id;

for (data *d = first[x]; d->u == x; d++) if (d->id != del_e) {

int y = d->v;

if (visit[y] == visit_id) continue;

dfs(y);

if (fail) return;

}

}

int main() {

scanf("%d%d", &n, &m);

if (n == 1) {

printf("1\n");

return 0;

}

for (int i = 0; i < m; i++) {

int u, v;

scanf("%d%d", &u, &v);

_edges[i * 2] = (data){u, v, i};

_edges[i * 2 + 1] = (data){v, u, i};

}

std::sort(_edges, _edges + 2 * m);

first[1] = _edges;

for (int i = 1; i < 2 * m; i++) {

if (_edges[i].u != _edges[i - 1].u) {

first[_edges[i].u] = _edges + i;

}

}

ans[0] = 2;

if (n == m) {

for (int i = 0; i < m; i++) {

del_e = i;

dfs_idx = 0;

ok = false;

fail = false;

dfs(1);

if (dfs_idx == n && ok && !fail) {

memcpy(ans, dfsseq, n * sizeof(int));

}

}

} else {

del_e = -2;

dfs(1);

memcpy(ans, dfsseq, n * sizeof(int));

}

for (int i = 0; i < n; i++) {

printf("%d%c", ans[i], " \n"[i + 1 == n]);

}

}

E.填数游戏

标程

#include <bits/stdc++.h>

using namespace std;

const int N=1e6+5;

const int mo=1e9+7;

typedef long long ll;

int n,m,f[N],g[N];

int Pow(int x,int y,int p){

int ans=1;

for(;y;y>>=1,x=(ll)x*x%p)if(y&1) ans=(ll)ans*x%p;

return ans;

}

int main(){

scanf("%d%d",&n,&m);

if(n>m) swap(n,m);

if(n==1){

printf("%d\n",Pow(2,m,mo)); return 0;

}

if(n==2){

printf("%d\n",4ll*Pow(3,m-1,mo)%mo); return 0;

}

if(n==3&&m==3){

puts("112"); return 0;

}

int ans=0,tmp=0;

//00,11

{

tmp=0;

tmp=Pow(4,n-2,mo);

tmp=(ll)tmp*Pow(3,m-n,mo)%mo;

tmp=(ll)tmp*Pow(2,n-1,mo)%mo;

ans=(ans+2ll*tmp)%mo;

}

//000,111

{

int k1=1;

for(int i=1;i<=4&&i<=n;i++) for(int j=1;j<=4&&j<=m;j++) if(i+j-1==4)++k1;

tmp=k1;

tmp=(ll)tmp*Pow(4,max(0,n-4),mo)%mo;

tmp=(ll)tmp*Pow(3,m-max(n,4),mo)%mo;

tmp=(ll)tmp*Pow(2,n-1,mo)%mo;

ans=(ans+2ll*tmp)%mo;

}

//011

{

memset(f,0,sizeof f); memset(g,0,sizeof g);

for(int i=1;i<=m;i++) f[i]=(i<=n?5:4); f[m+1]=3; g[m+1]=1;

for(int i=m;i>=1;i--) g[i]=(ll)g[i+1]*(f[i]-1)%mo;

int k1=0,k2=0;

for(int i=4;i<=m-1;i++){

int cur=(ll)(f[i]-1)*f[i+1]%mo*g[i+2]%mo;

k1=(k1+cur)%mo;

}

k1=(ll)k1*Pow(2,n-1,mo)%mo;

k2=(ll)f[m]*f[m+1]%mo*Pow(2,n-2,mo)%mo;

ans=(0ll+ans+k1+k2)%mo;

}

//001

{

if(n==3){

int k1=4ll*Pow(3,m-4,mo)%mo*Pow(2,n-1,mo)%mo;

ans=(ans+k1)%mo;

}else{

memset(f,0,sizeof f); memset(g,0,sizeof g);

for(int i=1;i<=n;i++) f[i]=(i<=n?5:4); f[n+1]=(n==m?3:4); g[n+1]=1;

for(int i=n;i>=1;i--) g[i]=(ll)g[i+1]*(f[i]-1)%mo;

int k1=0,k2=0;

for(int i=4;i<=n-1;i++){

int cur=(ll)(f[i]-1)*f[i+1]%mo*g[i+2]%mo;

k1=(k1+cur)%mo;

}

int tmpvalue=(n==m)?Pow(2,n-2,mo):(ll)Pow(3,m-n-1,mo)*Pow(2,n-1,mo)%mo;

k1=(ll)k1*Pow(3,m-n,mo)%mo*Pow(2,n-1,mo)%mo;

k2=(ll)f[n]*f[n+1]%mo*tmpvalue%mo;

ans=(0ll+ans+k1+k2)%mo;

}

}

printf("%d\n",2ll*ans%mo);

return 0;

}

F.保卫王国

标程

#pragma GCC diagnostic error "-std=c++11"
#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

const long long inf = 1e18;

int n,m,p[300100],f[300100][20],d[300100];

long long w[300100][20][2][2],up[300100][2],dp[300100][3];

vector<int> edge[300100];

void dfs(int now) {

dp[now][1] = p[now];

dp[now][0] = 0;

for (auto it = edge[now].begin();it != edge[now].end();it++)

if (*it != f[now][0]) {

f[*it][0] = now;

d[*it] = d[now] + 1;

dfs(*it);

dp[now][1] += dp[*it][2];

dp[now][0] += dp[*it][1];

}

dp[now][2] = min(dp[now][0],dp[now][1]);

}

void calc_up(int now) {

if (now > 1) {

up[now][1] = min(up[f[now][0]][1] + dp[f[now][0]][1] - dp[now][2],up[f[now][0]][0] + dp[f[now][0]][0] - dp[now][1]);

up[now][0] = up[f[now][0]][1] + dp[f[now][0]][1] - dp[now][2];

}

for (auto it = edge[now].begin();it != edge[now].end();it++)

if (*it != f[now][0])

calc_up(*it);

}

void doubling() {

for (int i = 1;i <= n;i++)

w[i][0][0][0] = inf,

w[i][0][0][1] = dp[f[i][0]][0] - dp[i][1],

w[i][0][1][0] = w[i][0][1][1] = dp[f[i][0]][1] - dp[i][2];

for (int d = 1;d < 20;d++)

for (int i = 1;i <= n;i++) {

int f0 = f[i][d - 1];

f[i][d] = f[f0][d - 1];

if (f[i][d]) {

for (int t1 = 0;t1 < 2;t1++)

for (int t2 = 0;t2 < 2;t2++)

w[i][d][t1][t2] = min(w[f0][d - 1][t1][0] + w[i][d - 1][0][t2],w[f0][d - 1][t1][1] + w[i][d - 1][1][t2]); // t1--up st, t2--down st

}

}

}

int lca(int x,int y) {

if (d[x] > d[y]) swap(x,y);

for (int i = 19;i >= 0;i--)

if (d[f[y][i]] >= d[x]) y = f[y][i];

for (int i = 19;i >= 0;i--)

if (f[y][i] != f[x][i])

x = f[x][i],

y = f[y][i];

if (x != y) return f[x][0];

return x;

}

long long query_chain(int x,int y,int sx,int sy) {

long long a[2],b[2];

a[sy] = dp[y][sy];

a[sy ^ 1] = inf;

for (int i = 19;i >= 0;i--)

if (d[f[y][i]] >= d[x]) {

b[0] = min(a[0] + w[y][i][0][0],a[1] + w[y][i][0][1]);

b[1] = min(a[0] + w[y][i][1][0],a[1] + w[y][i][1][1]);

a[0] = b[0];

a[1] = b[1];

y = f[y][i];

}

return a[sx];

}

long long query(int x,int y,int sx,int sy) {

if (d[x] > d[y]) swap(x,y),swap(sx,sy);

int l = lca(x,y);

if (l == x) return query_chain(x,y,sx,sy) + up[x][sx];

return min(query_chain(l,x,0,sx) + query_chain(l,y,0,sy) - dp[l][0] + up[l][0],query_chain(l,x,1,sx) + query_chain(l,y,1,sy) - dp[l][1] + up[l][1]);

}

char type[10];

int main() {

//freopen("defense.in","r",stdin);

//freopen("defense.out","w",stdout);

scanf("%d%d%s",&n,&m,type);

for (int i = 1;i <= n;i++) scanf("%d",p + i);

int u,v;

for (int i = 1;i < n;i++) {

scanf("%d%d",&u,&v);

edge[u].push_back(v);

edge[v].push_back(u);

}

f[1][0] = 0;

d[1] = 1;

dfs(1);

up[1][0] = up[1][1] = 0;

calc_up(1);

doubling();

int a,x,b,y;

while (m--) {

scanf("%d%d%d%d",&a,&x,&b,&y);

long long ans = query(a,b,x,y);

if (ans < inf) printf("%lld\n",ans);

else puts("-1");

}

return 0;

}

标程二

#pragma GCC diagnostic error "-std=c++11"

#include <cstdio>

#include <iostream>

#include <vector>

using namespace std;

int f[300100],p[300100];

long long dp[300100][3];

int a,x,b,y,n,m;

const long long inf = 1e18;

vector<int> edge[300100];

void dfs(int now) {

dp[now][1] = p[now];

dp[now][0] = 0;

for (auto it = edge[now].begin();it != edge[now].end();it++)

if (*it != f[now]) {

f[*it] = now;

dfs(*it);

dp[now][1] += dp[*it][2];

dp[now][0] += dp[*it][1];

}

if (a == now) dp[now][x ^ 1] = inf;

if (b == now) dp[now][y ^ 1] = inf;

dp[now][2] = min(dp[now][0],dp[now][1]);

}

long long query() {

dfs(1);

return dp[1][2];

}

char type[10];

int main() {

//freopen("defense.in","r",stdin);

//freopen("defense.ans","w",stdout);

scanf("%d%d%s",&n,&m,type);

for (int i = 1;i <= n;i++) scanf("%d",p + i);

int u,v;

for (int i = 1;i < n;i++) {

scanf("%d%d",&u,&v);

edge[u].push_back(v);

edge[v].push_back(u);

}

while (m--) {

scanf("%d%d%d%d",&a,&x,&b,&y);

long long ans = query();

if (ans < inf) printf("%lld\n",query());

else puts("-1");

}

return 0;

}