2019牛客暑期多校(第四场) 写题记录
A meeting
给了些关键点 在一棵树上 选取一个点让他们相聚 时间最短
其实就是求树直径 不过这次dfs完 我们找最远点的时候只看标记点 第二次dfs完也一样
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, m, cnt;
int head[maxn], d[maxn];
int to[maxn << 1], nxt[maxn << 1];
bool v[maxn];
void ade(int a, int b) {
to[++ cnt] = b;
nxt[cnt] = head[a];
head[a] = cnt;
}
void dfs(int x, int pre) {
for(int i = head[x]; i; i = nxt[i]){
int y = to[i];
if(y == pre) continue;
d[y] = d[x] + 1;
dfs(y, x);
}
}
int main(){
cin >> n >> m;
for(int i = 1, a, b; i < n; i ++) {
cin >> a >> b;
ade(a, b), ade(b, a);
}
for(int i = 1, a; i <= m; i ++) cin >> a, v[a] = 1;
d[1] = 0,dfs(1, -1);
int rt = -1, tmp = -1, ans = -1;
for(int i = 1; i <= n; i++ ) if(v[i] && d[i] > tmp) {
tmp = d[i];
rt = i;
}
d[rt] = 0, dfs(rt, -1);
for(int i = 1; i <= n; i ++ ) if(v[i] && d[i] > ans)
ans = d[i];
cout << (ans + 1) / 2 << endl;
return 0;
}
C sequence
on 是什么做法啊orz
给你一个长度n的序列 选取一个数字 和b包含它区间(而且它必须是这个区间的最小值) 使a[i]*(这一区间的和) 最大
首先单调栈 处理每个a[ i ] 管理区间(没有比它小的最大连续区间)
然后 对 a[ i ] 分2种情况 正负来考虑
大于 0 的情况 显然是 它 管理的区间和 *a[ i ] 因为a[i]>0 同时它肯定是这区间最低点 该区间越长和越大
小于 0 的情况 不妨我们维护一个 前缀和 既然它是负数 我们 当前i 到R[ i ]前缀和最好越小越好 而L[ i ] 到 i得和越大越好
#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
//#define int long long
using namespace std;
typedef long long ll;
const long long INF = 0x3f3f3f3f3f3f3f3f ;
const int maxn = 3e6 + 5 ;
int n;
ll a[maxn],sum[maxn], b[maxn];
int L[maxn],R[maxn];
struct node {
ll minsum,maxsum;
} tr[maxn<<2];
void pushup(int rt) {
tr[rt].minsum=min(tr[rt<<1].minsum,tr[rt<<1|1].minsum);
tr[rt].maxsum=max(tr[rt<<1].maxsum,tr[rt<<1|1].maxsum);
}
void build(int l,int r,int rt) {
if(l==r) {
tr[rt]={sum[l],sum[l]};
return ;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
ll maxquery(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R){
return tr[rt].maxsum;
}
int mid=(l+r)>>1;
ll res=-INF;
if(L<=mid) res=max(res,maxquery(L,R,l,mid,rt<<1));
if(R>mid) res=max(res,maxquery(L,R,mid+1,r,rt<<1|1));
return res;
}
ll minquery(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R){
return tr[rt].minsum;
}
int mid=(l+r)>>1;
ll res=INF;
if(L<=mid) res=min(res,minquery(L,R,l,mid,rt<<1));
if(R>mid) res=min(res,minquery(L,R,mid+1,r,rt<<1|1));
return res;
}
void solLR() {
stack<int> s;
for(int i=1; i<=n; i++) {
while(!s.empty()&&a[s.top()]>=a[i]) s.pop();
L[i]=(s.empty())?0:s.top();
s.push(i);
}
while(!s.empty()) s.pop();
for(int i=n; i>=1; i--) {
while(!s.empty()&&a[s.top()]>=a[i]) s.pop();
R[i]=(s.empty())?(n+1):s.top();
s.push(i);
}
}
signed main() {
scanf("%lld",&n);
for(int i=1; i<=n; i++) scanf("%lld",&a[i]);
for(int i=1; i<=n; i++) scanf("%lld",&b[i]),sum[i]=sum[i-1]+b[i];
solLR();
build(1,n,1);
ll ans=-INF;
ll rmin,lmax;
for(int i=1; i<=n; i++) {
if(a[i]<0) {
rmin=minquery(i,R[i]-1,1,n,1);
lmax=maxquery(L[i]+1,i,1,n,1);
ans=max(ans,a[i]*(rmin-lmax));
} else {
ans=max(ans,a[i]*(sum[R[i]-1]-sum[L[i]]));
}
}
printf("%lld\n",ans);
return 0;
}
D triples I
把这个数据拆成 21212121 的样子
n % 3 == 0 直接输出
n % 3 == 1 我们考虑 如果 补 1 够 2个 我们直接 n - b[1] n - b[0];
如果 二进制中贡献 1 的只有一个 我们选择 b[0] + c[0] 和 n - b[0];
else 我们选择 用 2位置补成3倍数 c[0] + c[1] + c[2] 和 n - c[0] - c[1];
n % 3 == 2 与上面相反
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<ll> b, c;
int main(){
int cas;
cin >> cas;
while(cas --) {
ll n;
cin >> n;
b.clear(), c.clear();
if(n % 3 == 0) {
cout << 1 << " " << n << endl;
} else {
ll x = 1;
ll i;
for(i = 0; x <= n; i ++) {
if((n >> i) & 1) {
if(x % 3 == 1) b.push_back(x);
else c.push_back(x);
}
x <<= 1;
}
if(n % 3 == 1) {
if(b.size() >= 2) cout << 2 << " " << n - b[1] << " " << n - b[0] << endl;
else if(b.size() == 1) cout << 2 << " " << b[0] + c[0] << " " << n - b[0] << endl;
else cout << 2 << " " << c[0] + c[1] + c[2] << " " << n - c[0] - c[1] << endl;
} else {
if(c.size() >= 2) cout << 2 << " " << n - c[1] << " " << n - c[0] << endl;
else if(c.size() == 1) cout << 2 << " " << b[0] + c[0] << " " << n - c[0] << endl;
else cout << 2 << " " << b[0] + b[1] + b[2] << " " << n - b[0] - b[1] << endl;
}
}
}
return 0;
}
J free
老题 分层图dj水过
#include <bits/stdc++.h>
#define A first
#define B second
using namespace std;
const int maxn = 1e3 + 10;
int head[maxn], cnt;
int nxt[maxn << 1], d[maxn << 1], to[maxn << 1];
int n, m, s, t, k;
void ade(int a, int b, int c) {
to[++cnt] = b;
d[cnt] = c;
nxt[cnt] = head[a];
head[a] = cnt;
}
typedef pair<int, int> P;
typedef pair<int, pair<int, int>> PP;
priority_queue<PP, vector<PP>,greater<PP> > que;
int dis[maxn][maxn];
bool vis[maxn][maxn];
void dj(){
memset(dis, 0x3f,sizeof (dis));
dis[s][0] = 0;
que.push(PP(0, P(s, 0))); /// DIS POS, K
while(!que.empty()){
P u = que.top().B; que.pop();
if(vis[u.A][u.B]) continue;
vis[u.A][u.B] = 1;
for(int i = head[u.A]; i; i = nxt[i]) {
int v = to[i];
if(dis[v][u.B] > dis[u.A][u.B] + d[i]) {
dis[v][u.B] = dis[u.A][u.B] + d[i];
que.push(PP(dis[v][u.B],P(v, u.B)));
}
if(u.B < k && dis[v][u.B + 1] > dis[u.A][u.B] ) {
dis[v][u.B + 1] = dis[u.A][u.B] ;
que.push(PP(dis[v][u.B + 1],P(v, u.B + 1)));
}
}
}
}
signed main() {
cin >> n >> m >> s >> t >> k;
for(int i = 1, a, b, c; i <= m; i ++) {
cin >> a >> b >> c;
ade(a, b, c), ade(b, a, c);
}
dj();
cout << dis[t][k] << endl;
return 0;
}
K number
比如说 123400
我们先统计单个0
ans += 2;
然后前缀和 123400
#… .% 3后 100111
我们可以整除300 的地方 只有 3 和 100 的倍数
也就是 2个0已经出现 0 对应的1 之前 第一个 1 之后的数据 就可以整除 300 记录余数 每次遇到便加上
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int sum[maxn], cnt[5];
char str[maxn];
int main(){
long long ans = 0;
cin >> (str + 1);
cnt[0] = 1;
int len = strlen(str + 1);
for(int i = 1; i <= len; i ++){
sum[i] = (sum[i - 1] + str[i] - '0') % 3;
if((str[i] - '0') == 0) ans += cnt[0];
}
for(int i = 1; i <= len; i ++ ) {
if(i + 1 <= len && str[i] == '0' && str[i + 1] == '0') ans += cnt[sum[i]];
cnt[sum[i]] ++;
}
cout << ans << endl;
return 0;
}
投递金山WPS等公司10个岗位 >