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

#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;

}

#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;

}

//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;

}

#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;

}