题解2023牛客寒假算法基础集训营2
Tokitsukaze and a+b=n (easy)
https://ac.nowcoder.com/acm/contest/46810/A
A Tokitsukaze and a+b=n (easy)
简单题，做法很多。
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
const int N = 2e5 + 10;
int vis[N],n;
int main() {
int T = read();
while(T--) {
memset(vis,0,sizeof(vis));
n = read();
int l = read(),r = read();
for(int i = l;i <= r;i++) vis[i] = 1;
l = read();r = read();
int ans = 0;
for(int i = l;i <= r;i++) {
if(n - i <= 0) continue;
ans += vis[n - i];
}
cout << ans << endl;
}
}
B Tokitsukaze and a+b=n (medium)
简单题，微微计算一下，画一个数轴理解。
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
const int N = 2e5 + 10;
int n;
int main() {
int T = read();
while(T--) {
n = read();
int l = read(),r = read();
int L = read(),R = read();
int t = l;
l = n - r;r = n - t;
if(l <= 0) l = 1;
// cout << "ce: " << l << " " << r << endl;
int ans = min(R,r) - max(l,L) + 1;
if(ans < 0) ans = 0;
cout << ans << endl;
}
}
C Tokitsukaze and a+b=n (hard)
中档题，根据 题的思路，我们其实就是要更好维护一下区间和，区间加，思路比较简单。我这里使用的是线段树，由于是有序组，最后答案乘 。
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
const int N = 2e6 + 10;
const ll mod = 998244353;
const int m = 4e5 + 10;
ll tot,n;
ll t[N],ans,tag[N];
void add(int u,int l,int r,int L,int R) {
if(L <= l && r <= R) {
tag[u] += 1;
t[u] += r - l + 1;
t[u] %= mod;
return ;
}
if(R < l || r < L) return;
int mid = l + r >> 1;
if(tag[u]) {
tag[u << 1] += tag[u];tag[u << 1 | 1] += tag[u];
t[u << 1] = (t[u << 1] + (mid - l + 1) * 1ll * tag[u] % mod) % mod;
t[u << 1|1] = (t[u << 1|1] + (r - mid) * 1ll * tag[u] % mod) % mod;
tag[u] = 0;
}
add(u << 1,l,mid,L,R);
add(u << 1 | 1,mid + 1,r,L,R);
t[u] = t[u << 1 | 1] + t[u << 1];
t[u] %= mod;
}
ll ask(int u,int l,int r,int L,int R) {
if(L <= l && r <= R) return t[u] % mod;
if(R < l || r < L) return 0;
int mid = l + r >> 1;
if(tag[u]) {
tag[u << 1] += tag[u];tag[u << 1 | 1] += tag[u];
t[u << 1] = (t[u << 1] + (mid - l + 1) * 1ll * tag[u] % mod) % mod;
t[u << 1|1] = (t[u << 1|1] + (r - mid) * 1ll * tag[u] % mod) % mod;
tag[u] = 0;
}
ll res = (ask(u << 1,l,mid,L,R)+ask(u << 1 | 1,mid + 1,r,L,R)) % mod;
t[u] = t[u << 1 | 1] + t[u << 1];
t[u] %= mod;
return res;
}
int main() {
int T = 1;
while(T--) {
memset(t,0,sizeof(t));
memset(tag,0,sizeof(tag));
ans = 0;
tot = read();n = read();
for(int i = 1;i <= n;i++) {
int l = read(),r = read();
ans = (ans + ask(1,1,m,l,r)) % mod;
if(tot - l >= 1) {
add(1,1,m,max(tot - r,1ll),tot - l);
}
}
cout << (ans * 2ll) % mod << endl;
}
}
D Tokitsukaze and Energy Tree
简单题，考虑到每一个节点在其父亲祖先节点算一次答案，所以我们用节点的深度排序，把最大深度的赋最大的值，然后计算和就行。
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
const int N = 2e5 + 10;
int n,si[N],val[N];
int main() {
n = read();si[1] = 1;
for(int i = 2;i <= n;i++) {
int fa = read();
si[i] = si[fa] + 1;
}
for(int i = 1;i <= n;i++) val[i] = read();
sort(val + 1,val + 1 + n);
sort(si + 1,si + 1 + n);
ll ans = 0;
for(int i = 1;i <= n;i++) {
ans += si[i] * 1ll * val[i];
}
cout << ans << endl;
}
E Tokitsukaze and Function
中档题，很容易通过什么数学的分析，得到最值是在 取得，但是这道题是只能取正整数，所以 或者 都有可能是最值。那么最值只会出现在 中。所以我们取其中的最小值，考虑到要求是最小的 ，所以我们要求这个 中的最小值，我这里用的是倍增，二分也行。（代码用的不是向上取整，但是不影响正确性）
using namespace std;
#define pii pair<int,int>
#define ll long long
ll read() {
ll x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
struct Node {
ll pos,val;
}a[6];
ll n,L,R;
bool cmp(Node x,Node y) {
return x.val < y.val;
}
ll f(ll x) {
return n / x + x - 1;
}
int main() {
int T = read();
while(T--) {
n = read();L = read();R = read();
ll sqr = (sqrt(n) + 0.5),top = 0;
a[++top] = (Node){L,f(L)};
a[++top] = (Node){R,f(R)};
if(L <= sqr && sqr <= R) a[++top] = (Node){sqr,f(sqr)};
if(L <= sqr + 1 && sqr + 1 <= R)a[++top] = (Node){sqr + 1,f(sqr + 1)};
sort(a + 1,a + top + 1,cmp);
ll ans = a[1].pos,val = f(a[1].pos);
for(ll i = 60;i >= 0;i--) {
ll res = ans - (1ll << i);
// cout << "val:: " << res <<" pos:: "<<val<< endl;
if(res < 1 || f(res) != val || res < L) continue;
ans = res;
}
printf("%lld\n",ans);
}
}
F Tokitsukaze and Gold Coins (easy)
简单题，考虑从起点和终点都来一次遍历，取交集。
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
const int N = 6e5 + 10;
int dp[N][4],n,k,vis[N][4];
int main() {
int T = read();
while(T--) {
n = read();k = read();
for(int i = 1;i <= k;i++) {
int x = read(),y = read();
vis[x][y] ^= 1;
}
dp[1][1] = 1;
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= 3;j++) {
if(!(dp[i][j] & 1) || vis[i][j]) continue;
if(vis[i + 1][j] == 0 && i != n) dp[i + 1][j] |= 1;
if(vis[i][j + 1] == 0 && j != 3) dp[i][j + 1] |= 1;
}
}
if(dp[n][3] != 1) {
cout << "0" << endl;
// return 0;
}
else {
dp[n][3] |= 2;
for(int i = n;i >= 1;i--) {
for(int j = 3;j >= 1;j--) {
if(!(dp[i][j] & 2) || vis[i][j]) continue;
if(vis[i - 1][j] == 0 && i != 1) dp[i - 1][j] |= 2;
if(vis[i][j - 1] == 0 && j != 1) dp[i][j - 1] |= 2;
}
}
int ans = 0;
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= 3;j++) {
if(dp[i][j] == 3) ans ++;
}
}
cout << ans - 1 << endl;
}
// cout << "SEE "<<endl;
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= 3;j++) {
// cout << dp[i][j] << " ";
dp[i][j] = vis[i][j] = 0;
}
// cout << endl;
// why？
}
}
}
/*
1
5 3
3 2
4 2
5 1
*/
G Tokitsukaze and Gold Coins (hard)
不会，留坑。
H Tokitsukaze and K-Sequence
中档题，贪心，每一次新加一个序列，我们都把现在第一序列中的每一个数字拿一个出来。然后记住当最大集合有 个的时候，对答案的贡献是 。
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
const int N = 1e5 + 100;
int n,T,a[N],b[N],vis[N];
vector<int> t[N];
int main() {
int T = read();
while(T--) {
memset(vis,0,sizeof(vis));
n = read();
int Ans = 0;
for(int i = 1;i <= n;i++) {
a[i] = read();
b[i] = a[i];
vis[a[i]]++;
}
sort(b + 1,b + 1 + n);
int len = unique(b + 1,b + 1 + n) - b - 1;
for(int i = 1;i <= len;i++) t[vis[b[i]]].push_back(b[i]);
int res = len;
Ans += t[1].size();len -= t[1].size();
printf("%d\n",Ans);
for(int i = 2;i <= n;i++) {
Ans += len;
Ans += t[i].size();
len -= t[i].size();
printf("%d\n",Ans);
}
for(int i = 1;i <= n;i++) t[i].clear();
}
}
I Tokitsukaze and Musynx
中档题，对整个序列做差分，每一个数字能改变值的次数是 次，所以离散化一下，然后从左到右依次遍历取 。
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
map<ll,ll> s;
ll val[6],n,c[6],a[200100],ans,sum;
int main() {
int T = read();
while(T--) {
n = read();
s.clear();
for(int i = 1;i <= n;i++) a[i] = read();
for(int i = 1;i <= 4;i++) c[i] = read();
for(int i = 1;i <= 5;i++) val[i] = read();
ans = sum = n * val[1];
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= 3;j++) {
s[c[j] - a[i]] += val[j + 1] - val[j];
}
s[c[4] + 1 - a[i]] += val[5] - val[4];
}
for(auto it : s) {
sum += it.second;
ans = max(sum,ans);
}
cout << ans << endl;
}
}
J Tokitsukaze and Sum of MxAb
简单题，发现无论是 的值都是两个数字绝对值之和。然后考虑每个次数的出现次数是 。
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
ll a,n;
int main() {
int T = read();
while(T--) {
n = read();a = 0;
for(int i = 1;i <= n;i++) a = a + abs(read());
cout << (ll)a * n * 2 << endl;
}
}
K Tokitsukaze and Synthesis and Traits
中档题，应该是根号分治，但是我比赛时候没写出来。然后我直接考虑离线答案，开一个桶记录一下。（感觉复杂度还挺低的）
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
const int N = 2e5 + 10;
vector<int> G[N],vis[N];
vector<pii> e;
int n,m,q,ans[N];
int main() {
n = read();m = read();q = read();
for(int i = 1;i <= m;i++) {
int a = read(),b = read();
G[a].push_back(b);
G[b].push_back(a);
e.push_back(pii(a,b));
}
for(int Id = 1;Id <= q;Id++) {
int k = read();
for(int i = 1;i <= k;i++) {
int a = read();
vis[a].push_back(Id);
}
}
for(int i = 1;i <= n;i++) sort(vis[i].begin(),vis[i].end());
for(int i = 0;i < m;i++) {
int x = e[i].first,y = e[i].second;
int l = 0,r = 0;
while(l < vis[x].size() && r < vis[y].size()) {
if(vis[x][l] == vis[y][r]) ans[vis[x][l]]++,l++,r++;
else if(vis[x][l] < vis[y][r]) l++;
else r++;
}
}
for(int i = 1;i <= q;i++) printf("%d\n",ans[i]);
}
L Tokitsukaze and Three Integers
简单题，容斥一下。减去两个相同，三个相同的。用桶记录答案就好。
using namespace std;
#define pii pair<int,int>
#define ll long long
ll read() {
ll x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
const int N = 5050;
ll n,p,a[N],vis[N],ans[N];
ll mul(ll x,ll y) {return (1ll * x * y) % p;}
ll add(ll x,ll y) {return (x + y) % p;}
int main() {
n = read();p = read();
for(int i = 1;i <= n;i++) {
a[i] = read();
}
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= n;j++) {
vis[mul(a[i],a[j])]++;
}
}
for(int i = 1;i <= n;i++) {
for(int v = 0;v < p;v++) {
ans[add(v,a[i])] += vis[v];
}
}
//12 相同
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= n;j++) {
if(i == j) continue;
ans[add(mul(a[i],a[i]),a[j])]--;
}
}
//(1 or 2) 3 相同
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= n;j++) {
if(i == j) continue;
ans[add(mul(a[i],a[j]),a[i])]-=2;
}
}
// 123 相同
for(int i = 1;i <= n;i++) ans[add(mul(a[i],a[i]),a[i])]--;
for(int i = 0;i < p;i++) cout << ans[i] << " ";
cout << endl;
}
虾皮信息HR面43人在聊
查看5道真题和解析