先占个坑，~~突然发现可以把发布时间调早一点~~

D1T1 铺设道路

题面

虽然很多人在喊是原题，但是还是写下放下三种写法吧。
很容易想到解法，就是维护区间最小值，达到$O(nlogn)$的复杂度。
但是这样子的写法无论是时间上还是代码复杂度上都比不过正解。

#include<iostream>
#include<cstdio>
#define lt p<<1
#define rt (p<<1)|1
using namespace std;
const int MAXN =100000;
int n,cnt,ans;
struct segT{
    int r,l,num,id;
}tree[MAXN*4];

void build(int p,int l,int r){
    tree[p].r=r,tree[p].l=l;
    if(l==r){
        scanf("%d",&tree[p].num);
        tree[p].id=++cnt;
        return;
    }
    int mid=(l+r)>>1;
    build(lt,l,mid);
    build(rt,mid+1,r);
    if(tree[lt].num>tree[rt].num){
        tree[p].num=tree[rt].num;
        tree[p].id=tree[rt].id;
    }
    else {
        tree[p].num=tree[lt].num;
        tree[p].id=tree[lt].id;
    }
}

int ask(int p,int ql,int qr){
    if(tree[p].l>=ql&&tree[p].r<=qr){
        return p;
    }
    int mid=(tree[p].l+tree[p].r)/2;
    if(mid>=qr)return ask(lt,ql,qr);
    if(mid<ql)return ask(rt,ql,qr);
    int o1=ask(lt,ql,qr),o2=ask(rt,ql,qr);
    if(tree[o1].num<tree[o2].num) return o1;
    else return o2;
}

void dfs(int l,int r,int sum){
    if(l>r)return;
    int tmp=ask(1,l,r);
    ans+=(tree[tmp].num-sum);
    dfs(l,tree[tmp].id-1,tree[tmp].num);
    dfs(tree[tmp].id+1,r,tree[tmp].num);
}

int main(){
    cin>>n;
    build(1,1,n);
    dfs(1,n,0);
    cout<<ans;
    return 0;
}

#include<iostream>

#include<cstdio>

#define lt p<<1

#define rt (p<<1)|1

using namespace std;

const int MAXN =100000;

int n,cnt,ans;

struct segT{

int r,l,num,id;

}tree[MAXN*4];

void build(int p,int l,int r){

tree[p].r=r,tree[p].l=l;

if(l==r){

scanf("%d",&tree[p].num);

tree[p].id=++cnt;

return;

}

int mid=(l+r)>>1;

build(lt,l,mid);

build(rt,mid+1,r);

if(tree[lt].num>tree[rt].num){

tree[p].num=tree[rt].num;

tree[p].id=tree[rt].id;

}

else {

tree[p].num=tree[lt].num;

tree[p].id=tree[lt].id;

}

int ask(int p,int ql,int qr){

if(tree[p].l>=ql&&tree[p].r<=qr){

return p;

}

int mid=(tree[p].l+tree[p].r)/2;

if(mid>=qr)return ask(lt,ql,qr);

if(mid<ql)return ask(rt,ql,qr);

int o1=ask(lt,ql,qr),o2=ask(rt,ql,qr);

if(tree[o1].num<tree[o2].num) return o1;

else return o2;

}

void dfs(int l,int r,int sum){

if(l>r)return;

int tmp=ask(1,l,r);

ans+=(tree[tmp].num-sum);

dfs(l,tree[tmp].id-1,tree[tmp].num);

dfs(tree[tmp].id+1,r,tree[tmp].num);

}

int main(){

cin>>n;

build(1,1,n);

dfs(1,n,0);

cout<<ans;

return 0;

}

考场上炸了（具体看我的退役记orz）写了一个$O(nm)$的复杂度的算法，m是数字的种类。（其实这个复杂度我也不是很确定）
然后测了4组数据，学军的和牛客的只有70，另外两组是100~~跑的还挺快~~，希望官方数据不要把我卡掉啊QAQ

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100003;
int a[MAXN];
int n;

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    long long ans=0;
    for(int i=1;i<=n;i++){
        while(a[i]!=0){
            int l=i,r=i;
            int mi=a[i];
            while(l-1>=1&&a[l-1]!=0)mi=min(a[--l],mi);
            while(r+1<=n&&a[r+1]!=0)mi=min(a[++r],mi);
            for(int j=l;j<=r;j++)a[j]-=mi;
            ans+=mi;
        }
    }
    cout<<ans<<endl;
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int MAXN=100003;

int a[MAXN];

int n;

int main(){

scanf("%d",&n);

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

long long ans=0;

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

while(a[i]!=0){

int l=i,r=i;

int mi=a[i];

while(l-1>=1&&a[l-1]!=0)mi=min(a[--l],mi);

while(r+1<=n&&a[r+1]!=0)mi=min(a[++r],mi);

for(int j=l;j<=r;j++)a[j]-=mi;

ans+=mi;

}

cout<<ans<<endl;

return 0;

}

正解只有12行，很容易想到，前面的如果比后面的高，肯定需要额外的操作来消除，记录入cnt即可

#include<bits/stdc++.h>
using namespace std;
int n,d[100005],cnt;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&d[i]);
        if(d[i]>d[i-1]) cnt+=d[i]-d[i-1];
    }
    cout<<cnt;
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int n,d[100005],cnt;

int main(){

scanf("%d",&n);

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

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

if(d[i]>d[i-1]) cnt+=d[i]-d[i-1];

}

cout<<cnt;

return 0;

}

还是想说下ccf这种恶劣的行为，又不是没有更好的题目，这样子真的是没意思……

D1T2 货币系统

题面

居然没有看出是完全背包！！！，一开始还用着自己智障的数学推论，结果最后还是打的深搜，60pt到85pt左右

#include<bits/stdc++.h>
using namespace std;
int n;
int a[112];
int flag;

void dfs(int now,int lim,int tar){
    if(now>tar||flag)return;
    if(now==tar){flag=1;return;}
    for(int i=1;i<=lim;i++){
        if(a[i]==-1)continue;
        dfs(now+a[i],lim,tar);
        if(flag)return;
    }
}

int main(){
    int t;scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int ans=n;
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        sort(a+1,a+1+n);
        for(int i=1;i<=n;i++){
            flag=0;
            dfs(0,i-1,a[i]);
            if(flag==1){
                ans--;a[i]=-1;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int n;

int a[112];

int flag;

void dfs(int now,int lim,int tar){

if(now>tar||flag)return;

if(now==tar){flag=1;return;}

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

if(a[i]==-1)continue;

dfs(now+a[i],lim,tar);

if(flag)return;

}

int main(){

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

while(t--){

scanf("%d",&n);

int ans=n;

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

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

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

flag=0;

dfs(0,i-1,a[i]);

if(flag==1){

ans--;a[i]=-1;

}

cout<<ans<<endl;

}

return 0;

}

正解其实有点像数论里面的筛法

考虑 $f[i]$ 表示价格 $i$ 能被出示， $f[0]=1$

由于大面值的钱不能表示小面值的，但小面值可能可以表示大面值的钱
我们对面值进行升序排序，对于每一个面值 $a[i]$ 它能表示的钱为 $x\times a[i] , x\in N$
于是我们遇到一个数 $a[i]$ 先判断 $a[i]$ 是否能被表示（即 $f[a[i]]$ 是否为1 ），如果能被表示，则答案减一，否则更新 $f$

~~这么简单没拿100真的很后悔~~

#include<bits/stdc++.h>
using namespace std;
int n;
int a[112];
bool f[25005];

int main(){
    int t;scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int ans=n;
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        sort(a+1,a+1+n);memset(f,0,sizeof(f));
        f[0]=1;
        for(int i=1;i<=n;i++){
            if(f[a[i]]){
                ans--;continue;
            }
            for(int j=a[i];j<=25000;j++)f[j]=f[j]|f[j-a[i]];
        }
        cout<<ans<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int n;

int a[112];

bool f[25005];

int main(){

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

while(t--){

scanf("%d",&n);

int ans=n;

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

sort(a+1,a+1+n);memset(f,0,sizeof(f));

f[0]=1;

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

if(f[a[i]]){

ans--;continue;

}

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

}

cout<<ans<<endl;

}

return 0;

}

D1T3 赛道修建

题面

考场40pt，实际上有55pt的部分分是很好拿的，这里只介绍AC做法，~~我被卡常了！！~~

看到最小的最大值，马上想到二分答案，但是如何判断这个答案是否可行呢？

虽然它图画的是方方正正的，但是它任然是一棵树，我们可以考虑自下向上的统计答案

显然一个子节点到父节点的道路只有一条，为了最优，我们希望子节点拿一条最长的路贡献给父节点

假设子节点能给父节点提供的长度为 $val_i$ （其中已经包含子节点到父节点路径长度）

该父节点首先要考虑能否选出满足二分答案k的赛道。

$k\leq val_i$ 这时这条赛道符合
$k\leq val_a+val_b $ 这时这两条路径组合成的道路符合

对于第一种情况我们很容易就能判断出，但是对于第二种情况，我们如果希望答案最优，就要从最小的 $val_a$ 考虑，为此，我们需要找到一个最小的 $val_b$ 使得 $k\leq val_a+val_b$

这个可以用 $multiset$ 来处理。

注意被选中的路径不能再贡献给当前节点的父节点了。

可以考虑找出树的直径优化二分上界。

在loj上最慢的点也才200ms，但是洛谷上T了两个点（怕不是要手写平衡树）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50005;
int Head[MAXN], Nt[MAXN << 1], to[MAXN << 1], w[MAXN << 1], tot = 1;
int n, m, sum;
int d[MAXN];
bool v[MAXN << 1];
int flag = 0;
int mx, mxid, res;

multiset<int> s[MAXN];
multiset<int>::iterator it;

void add(int a, int b, int c) {
    Nt[++tot] = Head[a];
    to[tot] = b;
    w[tot] = c;
    Head[a] = tot;
}

int dfs(int x, int fa, int k) {
    s[x].clear();
    int val;
    for (int i = Head[x]; i; i = Nt[i]) {
        int y = to[i];
        if (y == fa)
            continue;
        val = dfs(y, x, k) + w[i];
        if (val >= k)//已经满足条件，条数+1
            res++;
        else
            s[x].insert(val);
    }
    int maxx = 0;
    while (s[x].size()) {
        if (s[x].size() == 1) {//如果只有一个子节点（子树），直接返回
            return max(maxx, *s[x].begin());
        }
        it = s[x].lower_bound(k - *s[x].begin());//找到最小的x,使得x+最小值>=k
        if (it == s[x].begin() && s[x].count(*it) == 1)//如果找到的是最小值自己(即最小值两倍>=k)，但是最小值是唯一的，找下一个
            it++;
        if (it == s[x].end()) {//如果没找到
            maxx = max(maxx, *s[x].begin());//说明当前的最小值不行，请离场
            s[x].erase(s[x].find(*s[x].begin()));
        } else {
            res++;//如果找到了，条数+1
            s[x].erase(s[x].find(*it));//女嘉宾离场
            s[x].erase(s[x].find(*s[x].begin()));//男嘉宾离场
        }
    }
    return maxx;
}

void dfs1(int x) {
    for (int i = Head[x]; i; i = Nt[i]) {
        int y = to[i];
        if (v[y])
            continue;
        v[y] = 1;
        d[y] = d[x] + w[i];
        if (d[y] > mx) {
            mx = d[y];
            mxid = y;
        }
        dfs1(y);
    }
}

bool check(int k) {
    res = 0;
    dfs(1, 0, k);
    if (res >= m)
        return 1;
    return 0;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
        sum += c;
    }

    dfs1(1);
    int y = mxid;
    mx = 0;
    memset(v, 0, sizeof(v));
    memset(d, 0, sizeof(d));
    dfs1(y);

    int ans = 0;
    int l = 1;
    int r = mx;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else
            r = mid - 1;
    }
    printf("%d\n", ans);
    return 0;
}

100

101

102

103

104

105

106

107

108

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 50005;

int Head[MAXN], Nt[MAXN << 1], to[MAXN << 1], w[MAXN << 1], tot = 1;

int n, m, sum;

int d[MAXN];

bool v[MAXN << 1];

int flag = 0;

int mx, mxid, res;

multiset<int> s[MAXN];

multiset<int>::iterator it;

void add(int a, int b, int c) {

Nt[++tot] = Head[a];

to[tot] = b;

w[tot] = c;

Head[a] = tot;

}

int dfs(int x, int fa, int k) {

s[x].clear();

int val;

for (int i = Head[x]; i; i = Nt[i]) {

int y = to[i];

if (y == fa)

continue;

val = dfs(y, x, k) + w[i];

if (val >= k)//已经满足条件，条数+1

res++;

else

s[x].insert(val);

}

int maxx = 0;

while (s[x].size()) {

if (s[x].size() == 1) {//如果只有一个子节点（子树），直接返回

return max(maxx, *s[x].begin());

}

it = s[x].lower_bound(k - *s[x].begin());//找到最小的x,使得x+最小值>=k

if (it == s[x].begin() && s[x].count(*it) == 1)//如果找到的是最小值自己(即最小值两倍>=k)，但是最小值是唯一的，找下一个

it++;

if (it == s[x].end()) {//如果没找到

maxx = max(maxx, *s[x].begin());//说明当前的最小值不行，请离场

s[x].erase(s[x].find(*s[x].begin()));

} else {

res++;//如果找到了，条数+1

s[x].erase(s[x].find(*it));//女嘉宾离场

s[x].erase(s[x].find(*s[x].begin()));//男嘉宾离场

}

return maxx;

}

void dfs1(int x) {

for (int i = Head[x]; i; i = Nt[i]) {

int y = to[i];

if (v[y])

continue;

v[y] = 1;

d[y] = d[x] + w[i];

if (d[y] > mx) {

mx = d[y];

mxid = y;

}

dfs1(y);

}

bool check(int k) {

res = 0;

dfs(1, 0, k);

if (res >= m)

return 1;

return 0;

}

int main() {

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

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

int a, b, c;

scanf("%d%d%d", &a, &b, &c);

add(a, b, c);

add(b, a, c);

sum += c;

}

dfs1(1);

int y = mxid;

mx = 0;

memset(v, 0, sizeof(v));

memset(d, 0, sizeof(d));

dfs1(y);

int ans = 0;

int l = 1;

int r = mx;

while (l <= r) {

int mid = (l + r) >> 1;

if (check(mid)) {

ans = mid;

l = mid + 1;

} else

r = mid - 1;

}

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

return 0;

}

D2T1 旅行

又是一道本该拿满分的题，考场上打开题目->一眼看出基环树->只听过名字不会写->拿60pt愉快走人吧~

结果我完全忽视了8700k和n<=5000的存在，明显有一种平方的做法啊，就是暴力删边，然后就是一棵树了……mdzz

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5004;
vector<int> g[MAXN];
int n, m;
int num[MAXN], tmp[MAXN], cnt, dep;
bool v[MAXN];
struct edge
{
    int from, to;
} e[MAXN << 1];
int tot;
int k, z;

void add(int x, int y)
{
    e[++tot].from = x;
    e[tot].to = y;
}

void dfs1(int x)
{
    for (int i = 0; i < (int)g[x].size(); i++)
    {
        int y = g[x][i];
        if (v[y])
            continue;
        v[y] = 1;
        num[++cnt] = y;
        dfs1(y);
    }
}

void dfs(int x)
{
    v[x] = 1;
    tmp[++dep] = x;
    for (int i = 0; i < g[x].size(); i++)
    {
        int to = g[x][i];
        if (v[to] || (to == k && x == z) || (to == z && x == k))
            continue;
        dfs(to);
    }
}

bool check()
{
    for (int i = 1; i <= n; i++)
    {
        if (tmp[i] == num[i])
            continue;
        if (tmp[i] > num[i])
            return false;
        else
            return true;
    }
}

int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f * x;
}

int main()
{
    n = read();
    m = read();
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        x = read();
        y = read();
        add(x, y);
        add(y, x);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for (int i = 1; i <= n; i++)
        sort(g[i].begin(), g[i].end());
    if (m == n - 1)
    {
        v[1] = 1;
        num[++cnt] = 1;
        dfs1(1);
        for (int i = 1; i <= cnt; i++)
        {
            printf("%d ", num[i]);
        }
    }
    else
    {
        for (int i = 1; i < tot; i += 2)
        {
            dep = 0;
            k = e[i].from, z = e[i].to;
            memset(v, 0, sizeof(v));
            dfs(1);
            if (dep < n)
                continue;
            if (num[1] == 0)
                for (int i = 1; i <= n; i++)
                    num[i] = tmp[i];
            else if (check())
                for (int i = 1; i <= n; i++)
                    num[i] = tmp[i];
        }
        for (int i = 1; i <= n; i++)
        {
            printf("%d ", num[i]);
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5004;

vector<int> g[MAXN];

int n, m;

int num[MAXN], tmp[MAXN], cnt, dep;

bool v[MAXN];

struct edge

{

int from, to;

} e[MAXN << 1];

int tot;

int k, z;

void add(int x, int y)

{

e[++tot].from = x;

e[tot].to = y;

}

void dfs1(int x)

{

for (int i = 0; i < (int)g[x].size(); i++)

{

int y = g[x][i];

if (v[y])

continue;

v[y] = 1;

num[++cnt] = y;

dfs1(y);

}

void dfs(int x)

{

v[x] = 1;

tmp[++dep] = x;

for (int i = 0; i < g[x].size(); i++)

{

int to = g[x][i];

if (v[to] || (to == k && x == z) || (to == z && x == k))

continue;

dfs(to);

}

bool check()

{

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

{

if (tmp[i] == num[i])

continue;

if (tmp[i] > num[i])

return false;

else

return true;

}

int read()

{

int x = 0, f = 1;

char ch = getchar();

while (!isdigit(ch))

{

if (ch == '-')

f = -1;

ch = getchar();

}

while (isdigit(ch))

{

x = x * 10 + ch - '0';

ch = getchar();

}

return f * x;

}

int main()

{

n = read();

m = read();

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

{

int x, y;

x = read();

y = read();

add(x, y);

add(y, x);

g[x].push_back(y);

g[y].push_back(x);

}

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

sort(g[i].begin(), g[i].end());

if (m == n - 1)

{

v[1] = 1;

num[++cnt] = 1;

dfs1(1);

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

{

printf("%d ", num[i]);

}

else

{

for (int i = 1; i < tot; i += 2)

{

dep = 0;

k = e[i].from, z = e[i].to;

memset(v, 0, sizeof(v));

dfs(1);

if (dep < n)

continue;

if (num[1] == 0)

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

num[i] = tmp[i];

else if (check())

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

num[i] = tmp[i];

}

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

{

printf("%d ", num[i]);

}

return 0;

}

D1T1 铺设道路

D1T2 货币系统

D1T3 赛道修建

D2T1 旅行

发送评论 编辑评论

发送评论编辑评论