10.27下午 考试总结

标签:tree   sort   nod   长度   这一   int   math   mount   code   

这几天一直在挂分,尤其今天挂了 100 多分,就 \(nm\) 离谱。

T1 mountion

Despritio

给你一个 \(n\) 位整数,去掉其中任意 \(k\) 个数字之后,剩下的数字按左右次序组成一个新的非负整数。

请求出这个非负整数。 若有前导零,不用输出。

对于 100% 的数据 \(n\leq 10^6\)

solution

这数据范围提示我们需要 $O(n) $ 或者 \(O(nlogn)\) 的写法。

按位贪心,显然最高位尽可能越小越好。

假设我们一共要选 \(m\) 个数,现在该选第 \(k\) 位上的数字,那么我们要求的其实是 \([last+1,n-(m-k)+1]\) 的最小值。

因为左端点要保证这一位选的数的位置要大于上一位选的数的位置。而右端点则要保证剩下的位每一位都至少选一个。

单调队列或者线段树优化一下就可以过了。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e6+10;
int n,m,l,r,last,cnt,flag;
int a[N],q[N],ans[N];
char ch[N];
int main()
{
	freopen("mountain.in","r",stdin);
	freopen("mountain.out","w",stdout);
    scanf("%s%d",ch+1,&m);
    n = strlen(ch+1);
    m = n-m;
    for(int i = 1; i <= n; i++) a[i] = ch[i] - ‘0‘;
    l = 1, r = 0;
    for(int i = 1; i <= n-m; i++)
    {
        while(l <= r && a[q[r]] > a[i]) r--;
        q[++r] = i;
    }   
    for(int i = n-m+1; i <= n; i++)
    {
    	while(l <= r && a[q[r]] > a[i]) r--;
    	q[++r] = i;
        while(l <= r && q[l] < last + 1) l++;
        if(a[q[l]] != 0) printf("%d",a[q[l]]), flag = 1;//判断是否有前导零
        last = q[l];
    }
    if(flag == 0) printf("%d",0);//剩下的全为零的话直接输出零就可以
	fclose(stdin); fclose(stdout);
    return 0;
}

T2 dye

Desprition

小镇上有 n 个人得了一种奇怪的病,他们两两熟悉并且可接触。现在有一 种疫苗可以治愈这种疾病,小 R 作为镇长,希望可以利用小镇财政为他们治病。 这种疫苗有种奇怪的特性,可以通过病人间的接触接种(即一个接种过的病人 i 接触一个未接种过的病人 j,则后者也被接种,费用是 \(p[i][j]\))。当然也可以通过医 护人员直接接种(费用是 \(a_i\))。上述两种方法对不同人的费用是不同的,现在小 R 拿到了医护人员提供的费用明细(每个人通过直接接种和其他人接触接种的费 用),求助你为他提供一个所有人都接种的最小总费用。

input

第一行包括一个整数 \(n\) ,表示人数, 编号为 \(1\)\(n\) 。 第二行到第 \(n+1\) 行,第 \(i+1\) 行有一个整数 \(ai\)。 第 \(n+2\) 行到第 \(2n+1\) 行,第 \(n+i+1\) 行有 \(n\) 个用空格分开的整数,第 \(j\) 个整数表示 \(p[i][j]\)

output

输出一行表示最小花费。

\(n\leq 300, a[i] \leq 10^6,p[i][j]\leq 10^6\)

sloution

最小生成树。

我们建立一个超级源,对于每一个点(病人)连一条 \(a_i\) 的边,表示这个病人靠医护人员救治。

显然最后的传播入径会形成一颗树。

然后我们要做的就是最小化整棵树的边权和。\(krusal\) 算法求解就可以。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1010;
int n,m,tot,w,ans,fa[N];
struct node
{
    int u,v,w;
}e[100010];
inline int read()
{
    int s = 0,w = 1; char ch = getchar();
    while(ch < ‘0‘ || ch > ‘9‘){if(ch == ‘-‘) w = -1; ch = getchar();}
    while(ch >= ‘0‘ && ch <= ‘9‘){s = s * 10 + ch - ‘0‘; ch = getchar();}
    return s * w;
}
void add(int x,int y,int w)
{
    e[++tot].u = x;
    e[tot].w = w;
    e[tot].v = y;
}
bool comp(node a,node b)
{
    return a.w < b.w;
}
int find(int x)
{
    if(fa[x] == x) return x;
    else return fa[x] = find(fa[x]);
}
int main()
{
    n = read();
    for(int i = 1; i <= n; i++)
    {
        w = read();
        add(0,i,w);
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            w = read();
            if(i != j) add(i,j,w);
        }
    }
    for(int i = 0; i <= n; i++) fa[i] = i;
    sort(e+1,e+tot+1,comp);
    int num = n+1;
    for(int i = 1; i <= tot; i++)
    {
        int fx = find(e[i].u); 
        int fy = find(e[i].v);
        if(fx == fy) continue;
        ans += e[i].w;
        fa[fx] = fy;
        if(--num == 1) break;
    }
    printf("%d\n",ans);
    fclose(stdin); fclose(stdout);
    return 0;
}

T3 tree

Desprition

小镇有 \(n\) 个建筑,建筑以及建筑间的道路形成一棵树。从建筑 \(a\) 到建筑 \(b\) 要 花费\(dis(a,b) xor M\) 秒。\((dis(a,b)\)表示 \(ab\) 间的航线长度,\(xor\) 为位运算中 的异或)。为保证安全,这些建筑的消息一直采用统一传输的方式,即在 \(n\) 个建 筑中挑选一个改为仓库,存储并分发消息。为了给仓库选址,小 R 想知道,建筑 \(i(1<=i<=n)\) 到其它所有建筑花费的时间之和。

input

第一行包含两个正整数 \(N,M\) 。 接下来 \(n-1\) 行,每行 3 个正整数 \(a,b,c\) ,表示 \(a,b\) 之间的道路长度为 \(c\)

对于 30% 的数据 \(m=0\) ,另有 20% 的数据 \(n\leq 2000\)

对于 100% 的数据 \(n\leq 10^5,m\leq 16\)

sloution

膜拜直接切掉的 \(lpj\) 神仙。

考试的时候想到了是换根 \(dp\) ,但奈何不会写,爪八了。

现在还不会,咕咕咕。

10.27下午 考试总结

标签:tree   sort   nod   长度   这一   int   math   mount   code   

原文地址:https://www.cnblogs.com/genshy/p/13886575.html

版权声明:完美者 发表于 2020-10-31 1:37:20。
转载请注明:10.27下午 考试总结 | 完美导航

暂无评论

暂无评论...