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