竞赛讨论区 > NOIP2018复赛普及组C++复赛标程+数据
头像
大圈啊00
编辑于 2018-11-20 17:36
+ 关注

NOIP2018复赛普及组C++复赛标程+数据

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

A.标题统计
标程
#include <iostream>

#include <cstdlib>

#include <string>


int main() {

freopen("title.in", "r", stdin);

freopen("title.out", "w", stdout);


std::string s;

std::getline(std::cin, s);

int cnt = 0;

if (s.length() > 0 && s[0] != ' ') ++cnt;

if (s.length() > 1 && s[1] != ' ') ++cnt;

if (s.length() > 2 && s[2] != ' ') ++cnt;

if (s.length() > 3 && s[3] != ' ') ++cnt;

if (s.length() > 4 && s[4] != ' ') ++cnt;

std::cout << cnt << std::endl;


return 0;

}


B.***
标程

#include <cstdio>

#include <climits>


typedef long long LL;


const int N = 100010;


int n, m, p1;

LL c[N], s1, s2;


LL ABS(LL x) { return x < 0 ? -x : x; }


int main() {

freopen("fight.in", "r", stdin);

freopen("fight.out", "w", stdout);


scanf("%d", &n);

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

scanf("%lld", &c[i]);

}

scanf("%d%d%lld%lld", &m, &p1, &s1, &s2);

LL sum = (m - p1) * s1, best = LLONG_MAX; int k = -1;

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

sum += (m - i) * c[i];

}

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

LL tmp = ABS(sum + (m - i) * s2);

if (tmp < best) {

best = tmp;

k = i;

}

}

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


return 0;

}


C.摆渡车
标程

//100pts 500 100 4e6

#include<cstdio>

#include<algorithm>


#define INF 2147483647


int n,m;

int data[1024];

int sum[1024];

int dp[1024][128];


int main()

{

freopen("bus.in","r",stdin);

freopen("bus.out","w",stdout);

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

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

scanf("%d",data+i);

std::sort(data+1,data+n+1);

for(int i=1;i<=n;++i)sum[i]=sum[i-1]+data[i];

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

for(int j=0;j<m;++j)

{

int now=data[i]+j;

if(j)dp[i][j]=dp[i][j-1];

else dp[i][j]=now*i-sum[i];

for(int last=std::max(now-2*m+1,0);last<=now-m;++last)

{

int x=std::lower_bound(data+1,data+n+1,last+1)-data-1;

int y=std::min(last-data[x],m-1);

int tmp=dp[x][y]+(i-x)*now-(sum[i]-sum[x]);

if(tmp<dp[i][j])dp[i][j]=tmp;

}

}

printf("%d\n",dp[n][m-1]);

fclose(stdin);

fclose(stdout);

return 0;

}



D.对称二叉树
标程

#include <cstdio>

#include <algorithm>


typedef unsigned long long ull;


const int N = 1000010;

const ull P = 1000000007;


int n, v[N], l[N], r[N], best = 1;

ull H[N << 1];


int dfs(int u, ull& pre, ull& suf, int& Virtual) {

if (u == -1) {

pre = suf = 1001;

Virtual = 1;

return 1;

}


ull lpre, lsuf; int lv;

int ln = dfs(l[u], lpre, lsuf, lv);

ull rpre, rsuf; int rv;

int rn = dfs(r[u], rpre, rsuf, rv);


Virtual = lv + rv;

pre = v[u] * H[ln + rn] + lpre * H[rn] + rpre;

suf = v[u] * H[ln + rn] + rsuf * H[ln] + lsuf;


if (lpre == rsuf) {

int tmp = ln + rn + 1 - Virtual;

// if (tmp > 1) {

//     printf("%d\n", tmp);

// }

best = std::max(best, tmp);

}

return ln + rn + 1;

}   // return num of node


void init() {

H[0] = 1;

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

H[i] = H[i - 1] * P;

}

}


int main() {

freopen("tree.in", "r", stdin);

freopen("tree.out", "w" ,stdout);


init();


scanf("%d", &n);

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

scanf("%d", &v[i]);

}

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

scanf("%d%d", &l[i], &r[i]);

}

ull pre, suf; int Virtual;

dfs(1, pre, suf, Virtual);


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


return 0;

}


欢迎加入牛客OI交流群:370123478,更多比赛信息和题解都会分享到群中~

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐