Contest1019 - 2019年天梯赛&省赛选拔

文章目录

A 上课点名
B 消灭复读机
C 拾取金币
D 同学聚会
E 木工的烦恼
F 数字游戏
G 子序列问题
H 下大雪了
I 丢失的数字
J 最大岛屿
K 山区修路

学如逆水行舟，不进则退。

A 上课点名

用两个堆将数列分成两部分，一个用来求最大(即第k小)，它的size正好是要求的k,一个用来求最小,更新之前的堆

B 消灭复读机

将所有的连通图求出来，每个连通图都用一个vector<pair<int,int>> 表示，然后排序，用所有的点减去最小的点，然后用一个map<vector<pair<int,int>> 记录最多的图案

C 拾取金币

用之前所有的时间点去更新当前时间，用时间差和距离判断可否更新
复杂度O(m^2) dp

const int maxn = 1e4+10;
// int dp[maxn][maxn];
int dp[maxn];
LL t[maxn],x[maxn],y[maxn];
LL dis(LL x,LL y,LL x1,LL y1){
    return abs(x1-x)+abs(y1-y);
}
int main(void)
{
   int n,m;
   cin>>n>>m;
   int ans = 0;
   for(int i = 1;i <= m; ++i){
      scanf("%lld%lld%lld",&t[i],&x[i],&y[i]);
      dp[i] = 1;
      for(int j = 1;j < i; ++j){
         if(dis(x[j],y[j],x[i],y[i]) <= t[i]-t[j])
            dp[i] = max(dp[i],dp[j]+1);
      }
      ans = max(ans,dp[i]);
   }
   cout<<ans<<endl;
    

   return 0;
}

D 同学聚会

模拟即可，字符最好用数组来读，这样不会出错

E 木工的烦恼

注意是分成T块，不是切T刀
面积相等，我们可以枚举每一刀的位置，因为每一刀左右两边的面积应该都是x*y/T 的整数倍，枚举左边有多少个块即可

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
#define me(ar) memset(ar,0,sizeof(ar))
#define Pb push_back
const double pi = acos(-1.0);
const LL mod = 1e9+7;
LL qpow(LL a,LL b){
    LL s= 1;
    while(b > 0){
        if(b&1) s = s*a%mod;
        a = a*a%mod;
        b >>= 1;
    }
    return s;
}
LL gcd(LL a,LL b){
    return b?gcd(b,a%b):a;
}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
double x,y;
int T;
double rate(double x,double y){
    return max(x,y)/min(x,y);
}
double dfs(double x,double y,int T){
    if(T == 0) return rate(x,y);
    double ans = 1e5;
    int TT = T+1;
    for(int i = 1;i <= TT/2; ++i){
        double fen = x/TT;
        ans = min(ans,max(dfs(fen*i,y,i-1),dfs(fen*(TT-i),y,TT-i-1)));
    }
    for(int i = 1;i <= TT/2; ++i){
        double fen = y/TT;
        ans = min(ans,max(dfs(x,fen*i,i-1),dfs(x,fen*(TT-i),TT-i-1)));
    }
    return ans;
}
int main(void){
    cin>>x>>y>>T;
    T--;
    printf("%.6f\n",dfs(x,y,T));  
    return 0;
}

F 数字游戏

施工中

G 子序列问题

教练说，应该有这种觉悟，看到什么问题就想到什么算法
对于本题

看到子序列就应该想到dp
看到u到v的路径就应该想到lca
f = lca(u,v)
从u -> f 找子序列
从v -> f 反着找子序列
如果两头能对着，就存在这个子序列



const int maxn = 1e5+10;

const int maxlogv = 17;
struct Edge{
    int to,weight;
    Edge(int t,int w):to(t),weight(w){};
};
vector<Edge> G[maxn];
int w[maxn];
int id[maxn],dis[maxn];
int vs[maxn*2],depth[maxn*2];
int dp[maxn*2][maxlogv];
int DP[maxn][101];
void dfs(int node,int fa,int d,int &k){
    if(fa != -1) 
        for(int i = 1;i <= 100; ++i) 
            DP[node][i] = DP[fa][i];
    DP[node][w[node]] = node;  
    id[node] = k;
    vs[k] = node;
    depth[k++] = d;
    // dis[node] = distance;
    for(int i = 0;i < (int)G[node].size(); ++i){
        Edge &t = G[node][i];
        if(t.to == fa) continue;
        dis[t.to] = dis[node]+t.weight;
        dfs(t.to,node,d+1,k);
        vs[k] = node;
        depth[k++] = d;
    }
}

void init_rmq(int n){
    for(int i = 0;i < n ; ++i) dp[i][0] = i;
    for(int j = 1;(1<<j) <= n; ++j){
        for(int i = 0;i + (1<<j)-1 < n; ++i){
            if(depth[dp[i][j-1]]< depth[dp[i+(1<<(j-1))][j-1]])
                dp[i][j] = dp[i][j-1];
            else
                dp[i][j] = dp[i+(1<<(j-1))][j-1];

        }
    }
}
int query(int l,int r){
    int k = 0;
    while((1<<(k+1)) <= r-l+1) k++;
    if(depth[dp[l][k]] < depth[dp[r-(1<<k)+1][k]])
        return dp[l][k];
    else 
        return dp[r-(1<<k)+1][k];
}
int lca(int u,int v){
    return vs[query(min(id[u],id[v]),max(id[u],id[v]))];
}
void init(int n){
    int k = 0;
    dfs(0,-1,0,k);
    init_rmq(2*n-1);
}
int a[maxn];
int main(void)
{
    int n,q,m;
    cin>>n>>m;
    int u,v;
    rep(i,0,n-1){
        scanf("%d%d",&u,&v);
        u--,v--;
        G[u].Pb(Edge(v,1));
        G[v].Pb(Edge(u,1));
    }
    // cout<<endl;
    rep(i,0,n) scanf("%d",&w[i]);
    // cout<<endl;
    for(int i = 0;i < n; ++i)
        for(int j = 1;j <= 100; ++j) 
             DP[i][j] = INF;

    init(n);
    // cout<<endl;
    // cout<<endl;
    cin>>q;
    // cout<<q<<endl;
    while(q--){
        int k; scanf("%d",&k);
        scanf("%d%d",&u,&v);
        u--,v--;
        for(int i = 1;i <= k; ++i) scanf("%d",&a[i]);
        int f = lca(u,v);
        int i;
        for(i = 1;i <= k; ++i){
            int F = DP[u][a[i]];
            if(F == INF) break;
            if(depth[F] < depth[f]) break;
            u = F;
        }
        // i--;
        // cout<<f<<endl;
        int j;
        for(j = k; j >= 1; --j){
            int F = DP[v][a[j]];
            if(F == INF) break;
            if(depth[F] < depth[f]) break;
            v = F;
        }
        // j++;
        // cout<<i<<" "<<j<<endl;
        if(i > j) puts("Yes");
        else       puts("No"); 
    }
    return 0;
}

H 下大雪了

板子题：有向图的强连通分量，蓝书模板

I 丢失的数字

板子题：直接敲大数板子，然后枚举0-9 即可（这不是最优的，但是最不费脑子的）

J 最大岛屿

同B的存储连通图的方法，自定义排序方式

K 山区修路

需要先离散化，即将高度排序得到b1… bn
dp[i][j] 代表第i块高度为 $b_{j}$ 时的最小值是多少
$d p [i] [j] = m i n (d p [i - 1] [k]) + a b s (a [i] - b [j]), k = 0, 1, 2.... j$

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <climits>
using namespace std;
int dp[505][505];
int a[505];
int b[505];


int main(){
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		for(int i = 0;i < n;i++){
			scanf("%d",&a[i]);
		}
		
		memcpy(b,a,n * sizeof(a[0]));
		sort(b,b+n);
		
		for(int i = 0;i < n;i++){
			for(int j = 0;j < n;j++){
			
				int t = INT_MAX;
				for(int k = 0;k <= j;k++){
					t = min(t,dp[i][k]);
				}
				dp[i+1][j] = t + abs(b[j] - a[i]);
			}
		}
		
		int ma = INT_MAX;
		for(int i = 0;i < n;i++){
			if(dp[n][i] < ma){
				ma = dp[n][i];
			}
		}
		
		reverse(a,a+n);
		for(int i = 0;i < n;i++){
			for(int j = 0;j < n;j++){
			
				int t = INT_MAX;
				for(int k = 0;k <= j;k++){
					t = min(t,dp[i][k]);
				}
				dp[i+1][j] = t + abs(b[j] - a[i]);
			}
		}
		
		int mi = INT_MAX;
		for(int i = 0;i < n;i++){
			if(dp[n][i] < ma){
				mi = dp[n][i];
			}
		}
		
		cout << min(mi,ma) << endl;
	}		
}