杭电多校个人补题

2024-08-30 11:28
文章标签 个人 补题 杭电多校

本文主要是介绍杭电多校个人补题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

全部感悟。

1.要学会就是分类讨论,比如大于n小于n等于n,什么的。各种特殊情况,要考虑到。

2.要学会根据题意进行讨论

一、第八场:

第一题:cats的k-xor

k进制表示。肯定就是a%k a/k%k a/(k*k)%k ....

我们会发现,如果说,在十进制下面 a+b=c的话那么肯定就是在很多进制下面都可以满足题意。

那么我们接着去讨论 a+b<c 和 a+b>c 的两种情况

我们会发现当a+b<c的时候,我们不管我们怎么样的在进制下面运算,都不会实现a+b=c。因为k进制表示都会进行%k,/k运算。

那么我们去考虑a+b>c的情况下。这个时候我们可以去枚举判断k是否合法。k如果小于等于根号下a+b的话。那么复杂度就会降低到log级别。为什么是根号a+b呢。因为我们可以很简单的理解一下。如果k>根号下(a+b)。那么a和b最多只有两位。且最高位相加肯定是小于k的。那么高位肯定不会发生进位了。 只需要判断低位是否满足即可。就是 a+b-k=c 那么移动一下。就是k=a+b-c。只需要判断这个特例就好了。

#pragma GCC optimize(2)
#include <bits/stdc++.h>using namespace std;#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1const int N = 1e3 + 20, M = 5e6 + 10, mod = 1e9 + 7;
int kxor(int a,int b,int k){int ans=0;int w=1;int c=0;while(a>0||b>0){c=(a+b)%k;a/=k;b/=k;ans+=c*w;w*=k;}return ans;
}
void solve() {int a,b,c;cin>>a>>b>>c;if(a+b==c) {cout << "-1" << "\n";return;}else if(a+b<c){cout<<"0\n";return ;}int ans=0;for(int i=2;i<=45000;i++){if(kxor(a,b,i)==c) ans++;}if(a+b-c>45000&&kxor(a,b,a+b-c)==c) ans++;cout<<ans<<"\n";
}signed main() {cin.tie(nullptr)->sync_with_stdio(false);// cout.setf(ios::fixed), cout.precision(4);t = 1;// cin >> t;while (t--) {solve();}return 0;
}

第二题:cats的电脑中毒:

其实我们就是要找到离三个串都很远的位置。找到那个位置的时间,就是整体最长的时间。

我们统计三个字符串的关系。

s1=s2=s3 离三个串都远

s1=s2!=s3 离s1 s2 远

s1=s3!=s2 离s1 s3 远

s2=s3!=s1 离s2 s3 远

那么我们最后统计一下距离。

然后最后我们找到次小距离和最小距离。我们找到中间那个平均就是最大的距离了。

#pragma GCC optimize(2)
#include <bits/stdc++.h>using namespace std;#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1
int t;
const int N = 1e3 + 20, M = 5e6 + 10, mod = 1e9 + 7;
int kxor(int a,int b,int k){int ans=0;int w=1;int c=0;while(a>0||b>0){c=(a+b)%k;a/=k;b/=k;ans+=c*w;w*=k;}return ans;
}
void solve() {int n;cin>>n;string s[10];cin>>s[1]>>s[2]>>s[3];int ans=0;int cnt[10];cnt[1]=cnt[2]=cnt[3]=0;for(int i=0;i<n;i++) {if (s[1][i] == s[2][i] && s[2][i] == s[3][i]) ans++;if (s[1][i] != s[2][i] && s[2][i] == s[3][i]) cnt[1]++;if (s[1][i]!=s[2][i]&&s[2][i]!=s[3][i]) cnt[2]++;if (s[1][i]==s[2][i]&&s[2][i]!=s[3][i]) cnt[3]++;} int a=cnt[1]+cnt[2]+ans;int b=cnt[2]+cnt[3]+ans;int c=cnt[3]+cnt[1]+ans;if(a==max(a,max(b,c))) cout<<(b+c)/2<<"\n";else if(b==max(b,max(a,c))) cout<<(a+c)/2<<"\n";else if(c==max(c,max(a,b))) cout<<(a+b)/2<<"\n";
}signed main() {cin.tie(nullptr)->sync_with_stdio(false);// cout.setf(ios::fixed), cout.precision(4);t = 1;// cin >> t;while (t--) {solve();}return 0;
}

第三题:cats的二分答案

其实就是让你求一下,mid>n的次数不能超过k次。

那么就统计答案就好。左边的答案和右边的答案。

1.我们会发现如果说,k的数值特别大的话。我们可以轻松得到。这个区间内的所有数字都是可以进行选择的。就是区间的长度

2.之后我们进行长度和次数的划分。左边的区间需要进行次数减去一,右边的区间进行次数不变。

每次到达每一个点的答案都应该+1。

#pragma GCC optimize(2)
#include <bits/stdc++.h>using namespace std;#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1
int t;
const int N = 1e3 + 20, M = 5e6 + 10, mod = 1e9 + 7;
unordered_map<int,int>mp[100];
int dp(int r,int d){if(r==0) return 0;if((1<<d)>r)return r;if(mp[d][r]) return mp[d][r];if(d==0) return mp[0][r]=dp(r-(r+1)/2,d)+1;else mp[d][r]=dp((r+1)/2-1,d-1)+1+dp(r-(r+1)/2,d);
}
void solve() {int l,r,k;cin>>l>>r>>k;if(k>60) cout<< r-l+1<<"\n";else cout<<dp(r-l+1,k)<<"\n";
}signed main() {cin.tie(nullptr)->sync_with_stdio(false);// cout.setf(ios::fixed), cout.precision(4);t = 1;cin >> t;while (t--) {solve();}return 0;
}

第四题:重力拼图

这个题很简单,就是外围的一圈一定可以加上去的。然后去计算横的可以到达的和竖可以到达的。

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false),cin.tie(0);int T,n,m,a,b,mx;for(cin>>T;T>0;T--){cin>>n>>m>>a>>b;if(n==1||m==1){cout<<n*m<<'\n';continue;}mx=0;if(a!=1&&a!=n)mx=max(mx,m-2);if(b!=1&&b!=m)mx=max(mx,n-2);cout<<n*2+m*2-4+mx<<'\n';}return 0;
}

第五题:cats的最小生成树。

其实就是模拟最小生成树的流程。首先把所有的边进行一个排序。对于重边和成环的情况。我们就去存储这一条边,对于可以直接删的边,我们就直接去删除这个最小生成树的边。然后我们收集不能删除的边。当我收集到一个最小生成树之后,删除可以删的边之后,那么我们直接把之前的那些重边和成环边加到要删除的队列里面。因为很简单我们就不需要再重新的进行排序和搜索了。直接扫一遍过去了。

#pragma GCC optimize(2)
#include <bits/stdc++.h>using namespace std;#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first    
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1const int N = 1e5 + 20, M = 5e6 + 10, mod = 1e9 + 7;int t, n, m, k, lim, res;
string sr;struct DSU {std::vector<int> f, siz;DSU() {}DSU(int n) {init(n);}void init(int n) {f.resize(n);std::iota(f.begin(), f.end(), 0);siz.assign(n, 1);}int find(int x) {while (x != f[x]) {x = f[x] = f[f[x]];}return x;}bool same(int x, int y) {return find(x) == find(y);}bool merge(int x, int y) {x = find(x);y = find(y);if (x == y) {return false;}siz[x] += siz[y];f[y] = x;return true;}int size(int x) {return siz[find(x)];}
};
struct node {int u, v, val, id;bool operator < (const node& rhs) const {return val < rhs.val;}
};void solve() {cin >> n >> m;vector<int> ans(m, -1);DSU dsu(n);vector<node> edge;for (int i = 0; i < m; i++) {int u, v, w;cin >> u >> v;u--, v--;if (u > v) swap(u, v);edge.push_back({u, v, i + 1, i});}sort(all(edge));int sel_num = 0, now = 1;vector<int> sel;// set<int> sel_next;map<int, map<int, set<int>>> mp;map<int, map<int, int>> cntmp;set<PII> sel_next;bool flag = false;for (int i = 0; i < m; i++) {auto [x, y, val, id] = edge[i];while (sel.size() == n - 1) {if (dsu.size(0) == n) {for (int j = 0; j < sel.size(); j++) {ans[sel[j]] = now;}sel.clear();now++;dsu.init(n);set<PII> sel_temp;priority_queue<int,vector<int>, greater<int>> ttemp;for (auto [x, y] : sel_next) {auto idx = *mp[x][y].begin();mp[x][y].erase(idx);// int fax = dsu.find(x), fay = dsu.find(y);ttemp.push(idx);// if (fax == fay) continue;// sel.push_back(idx);// dsu.merge(x, y);cntmp[x][y]--;if (cntmp[x][y] > 0) sel_temp.insert({x, y});}while (ttemp.size()) {auto id = ttemp.top();ttemp.pop();auto [x, y, val, _] = edge[id];int fax = dsu.find(x), fay = dsu.find(y);if (fax == fay) {sel_temp.insert({x, y});cntmp[x][y]++;mp[x][y].insert(id);}else {sel.push_back(id);dsu.merge(x, y);}}sel_next.clear();sel_next = sel_temp;}else {flag = true;break;}}if (flag) break;int fax = dsu.find(x), fay = dsu.find(y);if (fax == fay) {sel_next.insert({x, y});mp[x][y].insert(id);cntmp[x][y]++;continue;}dsu.merge(x, y);sel.push_back(id);}if (sel.size() == n - 1) {if (dsu.size(0) == n) {for (int j = 0; j < sel.size(); j++) {ans[sel[j]] = now;}}}for (int i = 0; i < m; i++)cout << ans[i] << " \n"[i == m - 1];
}signed main() {cin.tie(nullptr)->sync_with_stdio(false);// cout.setf(ios::fixed), cout.precision(4);t = 1;cin >> t;while (t--) {solve();}return 0;
}

第七场:

第一题故障机器人:

就是说你有k次不被击打的机会。

其实就是顺序遍历。维护最大值就行。然后如果血量小了,直接就可以使用次数。加回来

也可以直接二分答案,寻找次数。然后去check检查时候符合答案。

#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin>>T;
while(T--){int n,x,k;
cin>>n>>x>>k;
vector<int>a(n+1);
priority<int>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}for(int i=1;i<=n;i++){
x-=a[i];
q.push(a[i]);
if(k&&x<=0){
x+=q.top();
q.pop();
}
if(x<=0)break;
else ans=i;
}
cout<<ans<<"\n";}}

第二题:蛋糕上的草莓是蛋糕的灵魂。

其实就是让草莓的数量就是蛋糕数量的倍数就行,满足草莓尽可能大。

其实就很简单,如果刚开始草莓就是蛋糕的倍数,那么我们就不用切。

如果不是倍数的话,我们只需要切草莓,不需要切蛋糕。因为b一定是草莓最后数量的一个因子。

那么我们切不切蛋糕都无所谓。

只需要求得 2*n*x=c*y c是倍数。n是刀数。那么n=c*y/(2*x) 如何让n最小呢。c取得2*x/gcd(y,2*x);并且要满足n是整数。

#include <iostream>
using namespace std;
#define ll long longll x, y;ll gcd (ll a, ll b) {if (! b) return a;return gcd (b, a % b);
}void solve () {cin >> x >> y;if (! (x % y)) cout << y << " " << x / y << endl;else cout << y << " " << 2 * x / gcd (2 * x, y) << endl;
}int main () {ios::sync_with_stdio (false), cin.tie (nullptr), cout.tie (nullptr);int _ = 1; cin >> _;while (_ --) solve ();cout.flush ();return 0;
}

第三题

其实就是知道合成每一个药物的,合成药物数量和价值。

要记录单个超过1e9,以及合成药物超过1e9,那么求一下最后的答案。如果超过1e9次数超过1就是impossible.否则就看一下最后答案是否超过1e9.没有的话直接输出答案。否则仍然是Impossible.

#pragma GCC optimize(2)
#include <bits/stdc++.h>using namespace std;#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1
int t;
const int N = 1e3 + 20, M = 5e6 + 10, mod = 1e9 + 7;const int LIM=1e9;
vector<pair<int,int>>to[N];
int val[N],cnt[N],need[N],tot[N];
int inf[N];
void dfs(int u){if(need[u]>LIM){inf[u]=1;return;}if(to[u].empty()){tot[u]=val[u]*need[u];if(tot[u]>LIM){inf[u]=1;}return ;}for(auto [x,a]:to[u]){need[a]=need[u]*x;if(need[a]>LIM){inf[u]=1;continue;}dfs(a);if(inf[a]){inf[u]=1;continue;}tot[u]+=tot[a];}
}
void solve() {int n,k;cin>>n>>k;for(int i=1;i<=n;i++){val[i]=cnt[i]=need[i]=tot[i]=inf[i]=0;to[i].clear();}for(int i=1;i<=n;i++){int p;cin>>p;if(p==0){cin>>val[i];}else{int t;cin>>t;for(int j=1;j<=t;j++){int x,a;cin>>x>>a;to[i].push_back({x,a});}}}need[k]=1;dfs(k);int MAX=0,infcnt=0,ans=0;for(auto it :to[k]){if(inf(it.second)) infcnt++;else{MAX=max(MAX,tot[it.second]);ans+=tot[it.second];}}if(infcnt>1){cout<<"Impossible"<<endl;return;}else if(infcnt==0) ans-=MAX;if(ans>LIM) cout<<"Impossible"<<endl;else cout<<ans<<endl;return;
}signed main() {cin.tie(nullptr)->sync_with_stdio(false);// cout.setf(ios::fixed), cout.precision(4);t = 1;cin >> t;while (t--) {solve();}return 0;
}

第四题:战争游戏

其实我们会发现,如果说直径都小于r1*2。那么轰炸方,直接可以全覆盖整个图形,那么防守方跑到任何地方都没有用。

如果r1*2>=r2防守方同样也没有任何的地方进行逃跑。

#pragma GCC optimize(2)
#include <bits/stdc++.h>using namespace std;#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1
int t;
const int N = 1e3 + 20, M = 5e6 + 10, mod = 1e9 + 7;const int LIM=1e9;
vector<pair<int,int>>to[N];
int val[N],cnt[N],need[N],tot[N];
int inf[N];
vector<int>E[100010];
int dis[N];
void dfs(int u,int fa){dis[u]=dis[fa]+1;for(auto v:E[u]){if(v!=fa) dfs(v,u);}return ;
}void solve() {int n,s,r1,r2;cin>>n>>s>>r1>>r2;for(int i=1;i<=n-1;i++){}{int u,v;cin>>u>>v;E[u].push_back(v);E[v].push_back(u);}dfs(1,0);int id=1;for(int i=2;i<=n;i++){if(dis[i]>dis[id])id=i;}dfs(id,0);int len=0;for(int i=1;i<=n;i++)len=max(len,dis[i]);}signed main() {cin.tie(nullptr)->sync_with_stdio(false);// cout.setf(ios::fixed), cout.precision(4);t = 1;cin >> t;while (t--) {solve();}return 0;
}

第六场:

第一题:不省人事

就是先将所有的进行排序。如果前面一个t大于了s肯定就是不可以的。

还有就是如果第一个不是休息,而是直接上课也是不行的。

后面就直接模拟顺序,进行上课休息上课休息的区间判断就好。

#pragma GCC optimize(2)
#include <bits/stdc++.h>using namespace std;#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1
int t;
const int N = 1e3 + 20, M = 5e6 + 10, mod = 1e9 + 7;
struct Event{int s,t,type;Event():s(0),t(0),type(0){}Event(int _s,int _t, int _type=0){s=_s;t=_t;type=_type;}bool operator<(const Event &a) const{return s==a.s ?t<a.t:s<a.s;}bool contain(const Event &a) const{return s<=a.s&&a.t<=t;}
};void solve() {int n,m;cin>>n>>m;vector<Event>events;for(int i=0;i<n;i++){int b,e;cin>>b>>e;events.emplace_back(b,e,0);}for(int i=0;i<m;i++){int s,t;cin>>s>>t;events.emplace_back(s,t,1);}sort(events.begin(),events.end());for(int i=1;i<events.size();i++){if(events[i-1].t>events[i].s){cout<<"No\n";return;}}if(events.front().type!=1){cout<<"No\n";return;}Event maybe_wakeup;for(Event now : events){if(now.type==1){int s=now.s;int t=now.t;maybe_wakeup=Event(t,t+2*(t-s));}else{if(!maybe_wakeup.contain(now)){cout<<"No\n";return ;}}}cout<<"Yes"<<"\n";return;}signed main() {cin.tie(nullptr)->sync_with_stdio(false);// cout.setf(ios::fixed), cout.precision(4);t = 1;cin >> t;while (t--) {solve();}return 0;
}

第十场补题:

第一题:NOI2024

题目就是说,一定能够拿金牌的情况,就是说明最后的情况,一定是排名大于k的。如果排名小于k,那么肯定就是不行的。那么接下来,我们就进行计算。所以我们直接计算,每一场在我们前面的人数,那么肯定就可能最后的排名也在我们的前面,如果这个人数大于等于k那么肯定就是不行的。人数要对m-1取min。

#pragma GCC optimize(2)
#include <bits/stdc++.h>using namespace std;#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1const int N = 1e6 + 20, M = 5e6 + 10, mod = 1e9 + 7;
unsigned long long P = 233;int t, n, m, k, lim, res;
string sr;
unsigned long long p[N];void solve() {int n,m,k;cin>>n>>m>>k;int sum=0;for(int i=1;i<=n;i++){int a;cin>>a;sum+=a-1;}for(int i=1;i<=n;i++){int b;cin>>b;}if(sum<k||k==m){cout<<"YES"<<"\n";}else{cout<<"NO"<<"\n";}
}signed main() {cin.tie(nullptr)->sync_with_stdio(false);// cout.setf(ios::fixed), cout.precision(4);t = 1;cin >> t;while (t--) {solve();}return 0;
}

第二题:不基本子串结构

我们可以发现,其实最终的结果就是去寻找一个串的最大后缀匹配到另外一个串的最大前缀匹配。然后其他的部分就是顺位加上去。那么这样的一个串就是最大的。同时如果说一个串在另外一个串中出现了两次及其以上,那么肯定就是不行的。因为这样就不是最短的了。次数一定不相等。

首先用KMP进行模式匹配,看看匹配次数超过了两次及其以上。那么肯定就是不行的。

然后匹配次数等于,那么肯定就是输出字符串长度就行。

最后直接去字符串循环比较前后缀就行,找最大的匹配串。

#pragma GCC optimize(2)
#include <bits/stdc++.h>using namespace std;#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first    
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1const int N = 1e6 + 20, M = 5e6 + 10, mod = 1e9 + 7;
unsigned long long P = 233;int t, n, m, k, lim, res;
string sr;
unsigned long long p[N];void init(int n) {p[0] = 1;for (int i = 1; i <= n; i++)p[i] = p[i - 1] * P;
}template<typename T>
vector<int> KMP(const T& s) {int n = s.size();vector<int> pi(n, 0);for (int i = 1, j = 0; i < n; ++i) {while (j && s[i] != s[j]) j = pi[j - 1];if (s[i] == s[j]) ++j;pi[i] = j;}return pi;
}void solve() {string A, B;cin >> A >> B;if (A.size() < B.size()) swap(A, B);int cnt = 0;int n = A.size(), m = B.size();auto pi = KMP(B + '#' + A);for (int i = m + 1; i < m + n + 1; ++i)if (pi[i] == m) {cnt++;}if (cnt >= 2) cout << -1 << "\n";else if (cnt == 1) cout << n << "\n";else {// unsigned long long p1 = 0, p2 = 0;int pre_len = 0, suf_len = 0;string s1 = "", s2 = "";for (int i = 0; i < n && i < m; i++) {s1 = s1 + A[i];s2 = B[m - 1 - i] + s2;if (s1 == s2) pre_len = i + 1;}s1 = "", s2 = "";for (int i = 0; i < n && i < m; i++) {s1 += B[i];s2 = A[n - 1 - i] + s2;if (s1 == s2) suf_len = i + 1;}// for (int i = 0; i < n && i < m; i++) {//     p1 = p[i] * (A[i] - 'a') + p1;//     p2 = P * p2 + (B[m - 1 - i] - 'a');//     if (p1 == p2) pre_len = i + 1;// }// p1 = 0ull, p2 = 0ull;// for (int i = 0; i < n && i < m; i++) {//     p1 = p[i] * (B[i] - 'a') + p1;//     p2 = P * p2 + (A[n - 1 - i] - 'a');//     if (p1 == p2) suf_len = i + 1;// }// cout << pre_len << " " << suf_len << " +++\n";cout << n + m - max(pre_len, suf_len) << "\n";}
}signed main() {cin.tie(nullptr)->sync_with_stdio(false);// cout.setf(ios::fixed), cout.precision(4);t = 1;cin >> t;init(N - 1);while (t--) {solve();}return 0;
}

第三题:SunBain

我们清晰的发现,就是说。如果k等于1的时候,如果为奇数,那么肯定就是交替进行的操作。如果为奇数,那么肯定就是Alice先手胜利,否则就是Bob胜利。

其次考虑一下,k>=n的时候,我们会发现。alice可以直接拿走所有的东西。

k<n的时候。那么只要Bob对称的跟Alice拿,那么肯定能够制裁到alice。导致最后bob获胜。

#pragma GCC optimize(2)
#include <bits/stdc++.h>using namespace std;#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1const int N = 1e6 + 20, M = 5e6 + 10, mod = 1e9 + 7;
unsigned long long P = 233;int t, n, m, k, lim, res;
string sr;
unsigned long long p[N];void solve() {int n,k;cin>>n>>k;if(k==1){if(n%2) cout<<"A"<<"\n";else cout<<"B"<<"\n";}else{if(k>=n) cout<<"A"<<"\n";else cout<<"B"<<"\n";}
}signed main() {cin.tie(nullptr)->sync_with_stdio(false);// cout.setf(ios::fixed), cout.precision(4);t = 1;cin >> t;while (t--) {solve();}return 0;
}

第四题:scenery

我们发现其实从里面往外扩就行。知道l的max数值。r的min值,可以得到l-r的一个活动区间。代表在这个区间是可以实现这个操作的。如果最后的r-l得到的数值不能满足大于t的总和。那么肯定就是不行的。

#pragma GCC optimize(2)
#include <bits/stdc++.h>using namespace std;#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1const int N = 1e6 + 20, M = 5e6 + 10, mod = 1e9 + 7;
unsigned long long P = 233;int t, n, m, k, lim, res;
string sr;
unsigned long long p[N];void solve() {int n,m;int maxl,minr;int flag=0;cin>>n>>m;int sum=0;for(int i=1;i<=n;i++){int l,r,t;cin>>l>>r>>t;if(flag==1) continue;if(i==1){maxl=l;minr=r+1;sum+=t;if(t>r-l) flag=1;continue;}else{int ll=l;int rr=r;int temp=0;if(rr-sum-l>=t){maxl=max(l,ll-t);temp=1;}if(ll+sum+t<=r+1){minr=min(r+1,minr+t);temp=1;}sum+=t;if(!flag) flag=1;}}if(flag==0){cout<<"YES"<<"\n";}else{cout<<"NO"<<"\n";}
}signed main() {cin.tie(nullptr)->sync_with_stdio(false);// cout.setf(ios::fixed), cout.precision(4);t = 1;cin >> t;while (t--) {solve();}return 0;
}

第九场

怪物猎人

就是我们计算一下,x和y根据总血量k的情况。直接见到最后会变成什么样子的次数和机会。

如果两个是同时变成的0话,说明就是有一个一定不能达到最后。只能一个人变成0,而另外一个人不能变成0.

那么最后计算一下

#pragma GCC optimize(2)
#include <bits/stdc++.h>using namespace std;#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1const int N = 1e6 + 20, M = 5e6 + 10, mod = 1e9 + 7;
unsigned long long P = 233;int t, n, m, k, lim, res;
string sr;
unsigned long long p[N];void solve() {int x,y,k;cin>>k>>x>>y;if(x>y) swap(x,y);int t1=(k+x-1)/x;int t2=(k+y-1)/y;if(t1==t2){if(t1%2==0) cout<<"No\nYes\n";else cout<<"Yes\nNo\n";}else{cout<<"Yes\nYes\n";}}signed main() {cin.tie(nullptr)->sync_with_stdio(false);// cout.setf(ios::fixed), cout.precision(4);t = 1;cin >> t;while (t--) {solve();}return 0;
}

黑洞合并

我们通过合并会发现,不管我们通过什么样子的合并,都是会得到一种最后的结果。然后我们直接随便模拟一下就可以实现最后的结果。

#pragma GCC optimize(2)
#include <bits/stdc++.h>using namespace std;#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1const int N = 1e6 + 20, M = 5e6 + 10, mod = 1e9 + 7;
unsigned long long P = 233;int t, n, m, k, lim, res;
string sr;
unsigned long long p[N];void solve() {cin>>n;vector<int>w(n+10);for(auto &x:w) cin>>x;int r=n-1,res=0;while(r>0){res=(res+(w[0]*w[r]%mod*(w[0]+w[r])%mod)%mod)%mod;w[0]=(w[0]+w[r])%mod;r--;}cout<<res<<"\n";
}signed main() {cin.tie(nullptr)->sync_with_stdio(false);// cout.setf(ios::fixed), cout.precision(4);t = 1;cin >> t;while (t--) {solve();}return 0;
}

树上询问

我们首先通过线段树或者st表的方式找到区间【l,r】内距离最远的两点x和y,再判断x和y之间路径是否为【l,r】中所有的点。

可以用哈希判断,也可以使用路径上的max和路径上的min以及路径上的点数判断。

融合矿石:

我们使用两次的完全背包进行求最大值就行。因为每一种的矿石数量都是无限的,所以我们直接用完全背包进行求解就行的。

首先我们计算第一个dp,dp[i][j]  i就是用到第几个物品下,质量为j的所有情况的最大金辉石占比。

然后用这些最大值,再去跑第二个dp,得到最后背包容量为m的情况下的最大价值。

#pragma GCC optimize(2)
#include <bits/stdc++.h>using namespace std;#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first    
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1const int N = 1e5 + 20, M = 5e6 + 10, mod = 1e9 + 7;int t, n, m, k, lim, res;
string sr;void solve() {vector<int> v(10);for (auto &x : v) cin >> x;cin >> n >> m;vector<PII> a(n + 1);for (int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;vector<int> dp(m + 1, 0);vector<int> f(m + 1, 0);for (int i = 1; i <= n; i++) {for (int j = a[i].fi; j <= m; j++) {dp[j] = max(dp[j], dp[j - a[i].fi] + a[i].se);}}// for (int i = 1; i <= m; i++)//     cout << i << " " << dp[i] << " ---\n";for (int i = 1; i <= m; i++) {for (int j = i; j <= m; j++) {if (dp[i] == 0) continue;int te = dp[i] * 10 / i;if (te * i == dp[i] * 10) te--;// cout << i << " " << dp[i] << " " << te << " " << v[te] << " +++\n";// cout << i << " " << dp[n][i] << " " << te << " ---\n";f[j] = max(f[j], f[j - i] + i * v[te]);// cout << j << " " << f[j] << " " << f[j - i] << " " << i << " " << dp[i] << " " << v[te] << " ++++\n";}}int res = 0;for (int i = 0; i <= m; i++)res = max(res, f[i]);cout << res << "\n";
}signed main() {cin.tie(nullptr)->sync_with_stdio(false);// cout.setf(ios::fixed), cout.precision(4);t = 1;cin >> t;while (t--) {solve();}return 0;
}

小猫钓鱼:其实我们很容易发现,如果第一个人有对子,那么不管对方怎么出。都可以赢得比赛。因为第一个人的对子数量一定跟第二个人的对子数量是一样的。一共有那么多张牌。不是你有就是我有。就这样的道理。

#pragma GCC optimize(2)
#include <bits/stdc++.h>using namespace std;#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1const int N = 1e6 + 20, M = 5e6 + 10, mod = 1e9 + 7;
unsigned long long P = 233;int t, n, m, k, lim, res;
string sr;
unsigned long long p[N];void solve() {int n;cin>>n;vector<int>a(n);map<int,int>mpa,mpb;int flag=0;for(auto x:a){cin>>x;mpa[x]++;if(mpa[x]>=2) flag=1;}if(flag==1) cout<<"shuishui\n";else cout<<"sha7dow\n";
}signed main() {cin.tie(nullptr)->sync_with_stdio(false);// cout.setf(ios::fixed), cout.precision(4);t = 1;cin >> t;while (t--) {solve();}return 0;
}

第二场:

女神的睿智:我们会发现,最终的合并过程永远都是合并到左边那个点。并且一共才8个碎片,很好进行操作的。所以我们只需要判断第一个字符和第5个字符是否相同,如果相同直接输出,如果不同那么输出数量大的那个字符。

#pragma GCC optimize(2)
#include <bits/stdc++.h>using namespace std;#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1const int N = 1e6 + 20, M = 5e6 + 10, mod = 1e9 + 7;
unsigned long long P = 233;int t, n, m, k, lim, res;
string sr;
unsigned long long p[N];void solve() {string s;cin>>s;map<char,int>mp;for(auto x:s){mp[x]++;}if(s[0]==s[4]){cout<<s[0]<<"\n";}else{if(mp[s[0]]>mp[s[4]]) cout<<s[0]<<"\n";else if(mp[s[0]]==mp[s[4]]) cout<<"N\n";else cout<<s[4]<<"\n";}}signed main() {cin.tie(nullptr)->sync_with_stdio(false);// cout.setf(ios::fixed), cout.precision(4);t = 1;cin >> t;while (t--) {solve();}return 0;
}

URL划分:按照题意进行划分就行,不难,简单的模拟题。

#include<bits/stdc++.h>using namespace std;void solve(){string s;cin>>s;string cur="";int i=0;int c=0;while(i<(int)s.size()){if(s.substr(i,1) == "/") {if((c<2) || (c>=2 && cur.find('=') != -1))cout<<cur<<"\n";cur.clear();i++;c++;}else if(s.substr(i,3) == "://") {if((c<2) || (c>=2 && cur.find('=') != -1))cout<<cur<<"\n";cur.clear();i+=3;c++;}else{cur+=s[i];i++;}}
}
int main(){int t;cin>>t;while(t--)solve();
}

在A里面找有C的B。

需要用到两个算法一个是KMP算法,另外一个是AC自动机。

需要匹配四个字符串。 A B B‘ C 。 

第一个在B’中找到是否有C,我们可以轻易地发现这个过程直接使用kmp算法即可。(当然哈希判断也是可以的)

第二是判断A中有哪些B出现过。这个地方我们可以用很多次的kmp算法,同时也可以直接使用AC自动机。实现,扫描一遍实现是否匹配B中的词语。

鸡爪:我们可以清晰地发现。最多可以构建的鸡爪数量就是n/3.

那么我们尽可能地让多余的点数全部连接到1这个点上面,然后是2然后是3.

那么直接画图模拟就可以发现规律。

#include <bits/stdc++.h>using namespace std;#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1const int N = 3e5 + 10, M = 5e6 + 10, mod = 1e9 + 7;
const double eps = 1e-8;int t, n, m, k, lim, res;
string sr;void solve() {cin >> n;int num = n / 3;if (n == 1) {cout << 1 << " " << 2 << "\n";return;}if (n == 2) {cout << 1 << " " << 2 << "\n";cout << 1 << " " << 3 << "\n";return;}if (n == 3) {cout << 1 << " " << 2 << "\n";cout << 1 << " " << 3 << "\n";cout << 1 << " " << 4 << "\n";return;}if (n == 4) {cout << 1 << " " << 2 << "\n";cout << 1 << " " << 3 << "\n";cout << 1 << " " << 4 << "\n";cout << 1 << " " << 5 << "\n";return;}if (n == 5) {cout << 1 << " " << 2 << "\n";cout << 1 << " " << 3 << "\n";cout << 1 << " " << 4 << "\n";cout << 1 << " " << 5 << "\n";cout << 1 << " " << 6 << "\n";return;}if (n == 6) {cout << 1 << " " << 2 << "\n";cout << 1 << " " << 3 << "\n";cout << 1 << " " << 4 << "\n";cout << 1 << " " << 5 << "\n";cout << 2 << " " << 3 << "\n";cout << 2 << " " << 4 << "\n";return;}for (int i = 2; i <= 3 + num + (n - num * 3); i++)cout << 1 << " " << i << "\n";for (int i = 3; i <= num + 2; i++) {cout << 2 << " " << i << "\n";}for (int i = 4; i <= num + 1; i++)cout << 3 << " " << i << "\n";}
/*
*/signed main() {cin.tie(nullptr)->sync_with_stdio(false);// cout.setf(ios::fixed), cout.precision(4);t = 1;cin >> t;while (t--) {solve();}return 0;
}

传奇勇士小凯:其实就是求最长的一条路径。使得最大的贡献路径和最大。我们容易知道贡献其实就是1/p。由伯努利概型和几何分布可以轻松的得到这个关系。

#include <bits/stdc++.h>using namespace std;#define int128 __int128_t
#define int long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fi first    
#define se second
#define lowbit(x) x & -x
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) x << 1
#define rs(x) x << 1 | 1const int N = 3e5 + 10, M = 5e6 + 10, mod = 1e9 + 7;
const double eps = 1e-8;int t, n, m, k, lim, res;
string sr;int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}int lcm(int a, int b) {return a * b / gcd(a, b);
}void solve() {cin >> n;vector<vector<int>> edge(n);vector<int> p(n);for (int i = 0; i < n - 1; i++) {int u, v;cin >> u >> v;u--, v--;edge[u].push_back(v);edge[v].push_back(u);}for (auto &x : p) cin >> x;vector<int> dp(n, 0);int com15 = 1;for (int i = 2; i <= 15; i++)com15 = lcm(com15, i);function<void(int, int)> dfs = [&](int u, int fa) {for (auto v : edge[u]) {if (v == fa) continue;dfs(v, u);dp[u] = max(dp[u], dp[v]);}dp[u] += (15 * com15 / p[u]);};dfs(0, -1);int ans1 = gcd(dp[0], com15);cout << dp[0] / ans1 << "/" << com15 / ans1 << "\n";}
/*
*/signed main() {cin.tie(nullptr)->sync_with_stdio(false);// cout.setf(ios::fixed), cout.precision(4);t = 1;cin >> t;while (t--) {solve();}return 0;
}

这篇关于杭电多校个人补题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1120689

相关文章

HomeBank:开源免费的个人财务管理软件

在个人财务管理领域,找到一个既免费又开源的解决方案并非易事。HomeBank&nbsp;正是这样一个项目,它不仅提供了强大的功能,还拥有一个活跃的社区,不断推动其发展和完善。 开源免费:HomeBank 是一个完全开源的项目,用户可以自由地使用、修改和分发。用户友好的界面:提供直观的图形用户界面,使得非技术用户也能轻松上手。数据导入支持:支持从 Quicken、Microsoft Money

分布式系统的个人理解小结

分布式系统:分的微小服务,以小而独立的业务为单位,形成子系统。 然后分布式系统中需要有统一的调用,形成大的聚合服务。 同时,微服务群,需要有交流(通讯,注册中心,同步,异步),有管理(监控,调度)。 对外服务,需要有控制的对外开发,安全网关。

Java IO 操作——个人理解

之前一直Java的IO操作一知半解。今天看到一个便文章觉得很有道理( 原文章),记录一下。 首先,理解Java的IO操作到底操作的什么内容,过程又是怎么样子。          数据来源的操作: 来源有文件,网络数据。使用File类和Sockets等。这里操作的是数据本身,1,0结构。    File file = new File("path");   字

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析

2025届计算机毕业设计:如何构建Java SpringBoot+Vue个人健康档案管理系统?

✍✍计算机编程指导师 ⭐⭐个人介绍:自己非常喜欢研究技术问题!专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目:有源码或者技术上的问题欢迎在评论区一起讨论交流! ⚡⚡ Java实战 | SpringBoot/SSM Python实战项目 | Django 微信小程序/安卓实战项目 大数据实战项目 ⚡⚡文末获取源码 文章目录

【动手学深度学习】04 数据操作 + 数据预处理(个人向笔记)

数据操作 N维数组是机器学习和神经网络的主要数据结构其中 2-d 矩阵中每一行表示每一行表示一个样本 当维度来到三维的时候则可以表示成一张图片,再加一维就可以变成多张图片,再加一维则可以变成一个视频 访问元素 冒号表示从冒号左边的元素到冒号右边的前一个元素(开区间),其中如果左边为空,那么表示从第一个开始,如果右边为空,那么表示访问到最后一个,如果两边都为空,则表示全部访问其中一行中我们指

Thinkphp6.0+vue个人虚拟物品网站源码

Thinkphp6.0+vue个人虚拟物品网站源码 支持码支付对接 扫码自动发货 源码一共包含两个部分thinkphp6.0后端文件,以及vue前端文件。 服务器环境 php7以上,mysql5.6以上; 内附安装说明 代码免费下载

Windows目录及程序安装路径个人习惯

目录 一、系统盘IntelProgram FilesProgram Files (x86)ProgramDataWindowsUsers 二、软件盘360AdobeGameSoftMyIDESQLTencentWorkSoftXunLei 三、文件盘ApacheTencentDataMediaGameDataMyProject其他文件最终下载 视情况、或文中错误,而不定期更

分享个人学习和解决问题的的方法

1.自己去分析问题,去看源码 2.去百度搜索 3.去问同学同事朋友 4.去QQ群里问 除了自己解决,我最支持的是去QQ群里问, QQ群里有全国各地的程序员,有各种水平的程序员, 这样一个问题,会有各种各样的答案,学到更多的知识。 同时,我也建议大家去有空了去群里回答问题, 帮助别人的同时也可以自己学到知识,何乐而不为?

iOS开发——UI组件(个人整理)

最近把iOS里的UI组件重新整理了一遍,简单来看一下常用的组件以及它们的实现。其实现在这些组件都可以通过Storyboard很快的生成,只是要向这些组件能够变得生动起来并且赋予它们更具生命力的事件,还是需要一番功夫的。 UIButton 这儿有一篇教程,挺全的,可以参考下:http://www.cnblogs.com/chen1987lei/archive/2011/09/09/2172