T1

上来直接秒了组合数

#include<bits/stdc++.h>
#define ll long long
#define gt getchar
using namespace std;
inline ll read()
{
	ll x = 0, f = 1;char ch = gt();
	while(!isdigit(ch)){if(ch == '-')f = -1;ch = gt();}
	while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = gt();}
	return x * f;
}
const int mod = 1e9 + 7;
int x[1000006];
ll qpow(ll a, ll b)
{
	ll res = 1;
	while(b)
	{
		if(b & 1)res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
void file()
{
	freopen("cube.in", "r", stdin);
	freopen("cube.out", "w", stdout);
}
int main()
{
	//file();
	int n = read(), k = read();
	for(int i = 1; i <= n; ++ i)
	{
		x[i] = read();
	}
	ll nn = 1, kk = 1, nk = 1;
	for(int i = 1; i <= n; ++ i)
	{
		nn = (nn * i) % mod;
		if(i == k)kk = nn;
		if(i == n - k)nk = nn;
	}
	ll res =  (((nn * qpow(kk, mod - 2)) % mod) * qpow(nk, mod - 2)) % mod;
	cout << res << '\n';
	return 0;
}

T2

上来看了一会随便胡了个结果10pts

正解是二分答案

check里dp

\(f_i\) 表示前 \(i\) 个位置里保留 \(f_i\) 个，强制保留第 \(i\) 个

双重循环，可得方程 \(f_i = max(f_i, f _j + 1)\) 当且仅当两端数值之差除以区间长度小于对应check的答案

后面再循环一遍 \(d\) 若发现有值大于 \(n - k\) 则可以下调，否则上调

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
const int maxn = 1005;
int a[maxn], f[maxn]00  ;
int n, k;
bool check(int l)
{
    f[1] = 1;
    if(f[1] >= n - k)return 1;
    for(int i = 2; i <= n; ++ i)
    {
        for(int j = 1; j < i; ++ j)
        {
            if(abs(a[i] - a[j]) <= (i - j) * l)
            f[i] = max(f[i], f[j] + 1);
        }
    }
    for(int i = 1; i <= n; ++ i)
    {
        if(f[i] >= n - k)return 1;
    }
    return 0;
}
int main()
{
    n = read(), k = read();
    int mx = -1;
    for(int i = 1; i <= n; ++ i) a[i] = read(), mx = max(mx, a[i]);
    int L = 0, R = mx + 1;
    int Mid;
    int res = 0;
    while(L <= R)
    {
        for(int i = 0; i <= n + 1; ++ i)f[i] = 0;
        Mid = (L + R) >> 1;
        if(check(Mid))R = Mid - 1, res = Mid;
        else L = Mid + 1;
    }
    cout << res;
    return 0;
}

T3

相当于查找每个元素向左和向右的最小值所对应的位置，然后跑两边单调栈即可

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
	ll x=0,f=1;char ch=gt();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
	return x*f;}
const int maxn = 10000007;
int x[maxn], p[maxn], fa[maxn], s[maxn];
int top, Max;
int main()
{
	int n = read();
	for(int i = 1; i <= n; ++ i)
	{
		x[i] = read(), p[i] = read();
	}
	for(int i = 1; i <= n; ++ i)
	{
		while(top && p[s[top - 1]] < p[i])
			fa[s[-- top]] = i;
		s[top] = i;
		++ top;
	}
	top = 0;
	for(int i = n; i > 0; -- i)
	{
		while(top && p[s[top - 1]] < p[i])
		{
			-- top;	
			if(x[fa[s[top]]] - x[s[top]] > x[s[top]] - x[i] || fa[s[top]] == 0)fa[s[top]] = i;
			else if(x[fa[s[top]]] - x[s[top]] == x[s[top]] - x[i] && p[fa[s[top]]] < p[i])fa[s[top]] = i;

		}
		s[top] = i;
		++ top;
	}
	for(int i = 1; i <= n; ++ i)
	{
		if(fa[i])cout << fa[i] << ' ';
		else cout << -1 << ' ';
	}
	return 0;
}

T4

炸了，全输出0，等着调

但是交上去还有24分？

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=gt();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
    return x*f;}
const int maxn = 1000006;
int n;
int siz[maxn], light[maxn], tup[maxn], tdw[maxn], res[maxn];
struct edge
{
    int to, nxt;
}ed[maxn << 1];
int ecnt, head[maxn];
inline void add(int u, int v)
{
    ed[++ ecnt] = {v, head[u]}, head[u] = ecnt;
}
void dfs(int u, int fa)
{
    siz[u] = 1;
    for(int i = head[u], v = ed[i].to; i; i = ed[i].nxt)
    {
        if(v == fa)continue;
        dfs(v, u);
        siz[u] += siz[v];
    }
    if(light[u] == 0)
    {
        for(int i = head[u], v = ed[i].to; i; i = ed[i].nxt)
        {
            if(v == fa)continue;
            tdw[v] = max(tdw[v], siz[v]);
        }
        tup[u] = max(tup[u], n - siz[u]);
    }
}
int vis[maxn];
void dfs_up(int u, int fa)
{
    for(int i = head[u], v = ed[i].to; i; i = ed[i].nxt)
    {
        if(v == fa)continue;
        dfs_up(v, u);
        tup[u] = max(tup[u], tup[v]);
        res[u] = max(res[u], tup[v]);
    }
    int tot = 0;
    int mx = 0;
    
    for(int i = head[u], v = ed[i].to; i; i = ed[i].nxt)
    {
        if(v == fa)continue;
        vis[++ tot] = i;
        tdw[v] = max(tdw[v], mx), mx = max(mx, tup[v]);
    }
    mx = 0;
    for(int i = tot; i >= 1; -- i)
    {
        int v = ed[vis[i]].to;
        if(fa == v)continue;
        tdw[v] = max(tdw[v], mx), mx = max(mx, tup[v]);
    }
}
void dfs_down(int u,int fa)
{
    res[u] = max(res[u], tdw[u]);
    int tot = 0;
    for(int i = head[u], v = ed[i].to; i; i = ed[i].nxt)
    {
        if(v == fa)continue;
        vis[++ tot] = i;
    }
    for(int i = tot; i >= 1; -- i)
    {
        int v = ed[vis[i]].to;
        if(fa == v)continue;
        tdw[v] = max(tdw[v], tdw[u]);
        dfs_down(v, u);
    }
}
int main()
{
    n = read();
    int cnt = n;
    for(int i = 1; i <= n; ++ i)
        light[i] = read(), cnt -= light[i];
    for(int i = 1; i <= n - 1; ++ i)
    {
        int u = read(), v = read();
        add(u, v), add(v, u);
    }
    if(cnt % 2 == 0)
    {
        for(int i = 1; i <= n; ++ i)cout << n << '\n';
        return 0;
    }
    dfs(1, 0);
    dfs_up(1, 0);
    dfs_down(1, 0);
    for(int i = 1; i <= n; ++ i)cout << res[i] << '\n';
    return 0;
}