2024杭电8

本文主要是介绍2024杭电8，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
有一个n*m的矩阵，给出最开始拼图的位置。
可以有四个选择，设置重力的方向，就是拼图会向一个方向竖直掉落到最底。
问任意操作次数后拼图走过的方格数量最大值。

题解：
首先已经在边缘的拼图，只能沿着边走一圈，再判断最开始可以朝哪个方向移动是最大值。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef __int128 i128;
typedef long long ll;
typedef double db;const db PI = acos(-1);
typedef array<ll, 2> PII; // vector<PII> a(n + 1);
const ll inf = 2e18 + 10;
const int mod = 998244353;
const int maxn = 2e5 + 10;
bool multi = 1;void Solve() {ll n, m, a, b; cin >> n >> m >> a >> b;if(n == 1 || m == 1) {cout << n * m << "\n";return ;        }ll ans = n * 2 + m * 2 - 4;ll summ = 0;if(a > 1 && a < n) summ = max(m - 2, summ);if(b > 1 && b < m) summ = max(n - 2, summ);cout << ans + summ << "\n";
}signed main() {// freopen("test.in","r",stdin);  // freopen("code.out","w",stdout);    ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);ll T = 1;if(multi) cin >> T;while(T -- ) {Solve();}return 0;
}

题意：
给定$a,b,c$，使$a$和$b$的不进位$k$进制加法等于$c$
不进位$k$进制加法就是$a$和$b$的$k$进制数，每一位相加，但是不进位。
问有多少不同的$k$，假如有无数种可能性，就输出$-1$

题解：
首先$a+b=c$时就是$-1$，因为只要$k$足够大，没有进位就行了。
$a+b<c$答案是0，因为不进位加法只会变小，不会变大。

损失的值是$a+b-c$，损失的值都是$k$进制的某一位值，所有肯定也是k的倍数，那我们就枚举$a+b-c$的因数为$k$，判断一下是否符合要求。

代码：

#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
//#include "_my_utils.h" 
#endif// #define int long long
#define new _MY_NEW_using namespace std;
using ll = long long;
using PII = array<int, 2>;constexpr long long INF = 2E18 + 10;
constexpr int N = 4E4 + 10;
int s[N];
void SINGLE_TEST() 
{int a,b,c;cin>>a>>b>>c;// a=b=c=100000000;if(a+b==c){cout<<-1<<"\n";return ;}if(a+b<c){cout<<"0\n";return ;}// auto ch=[&](int k,int x){//     vector<int> res;//     while(x>0){//         res.push_back(x%k);//         x/=k;//     }//     return res;// };int ans=0;// int cnt=0;int xx=a+b-c,cnt=0;for(int i=2;i*i<=xx;i++){if(xx%i==0){s[++cnt]=i;if(xx/i!=i){s[++cnt]=xx/i;}}}s[++cnt]=xx;for(int j=1;j<=cnt;j++){int i=s[j];vector<int> x,y,z;int aa=a,bb=b,cc=c;int k=i;while(aa>0){x.push_back(aa%k);aa/=k;// cnt++;}while(bb>0){y.push_back(bb%k);bb/=k;// cnt++;}while(cc>0){z.push_back(cc%k);cc/=k;// cnt++;}auto sz=max({x.size(),y.size(),z.size()});while(x.size()<sz)x.push_back(0);while(y.size()<sz)y.push_back(0);while(z.size()<sz)z.push_back(0);// debug(x);debug(y);debug(z);bool ok=1;for(int j=0;j<sz;j++){// cnt++;if((x[j]+y[j])%i!=z[j]){ok=0;break;}}
//        if(ok)cout<<i<<' ';ans+=ok;}// int b1=a/N,b2=b/N,b3=c/N;// if((b1+b2)==b3){//     a=a%N;//     b=b%N;//     c=c%N;//     if(a+b==c) ans++;// }cout<<ans<<"\n";
}signed main(){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int SAMPLES = 1;cin >> SAMPLES;for(int CUR=1;CUR<=SAMPLES;CUR++){SINGLE_TEST();}
}

题意：
给定$l,r,k$，一个数组的左边界是$l$,右边界n在$[l,r]$之间。
在$[l,r]$二分找右边界，假如mid在数组外就是越界。
问在越界不超过k次的情况下，有多少右边界可以被二分查找到。

题解：
就是dfs一下，每次递归$[l,mid-1]$,$[mid+1,r]$.
用map记录区间大小和越界次数，避免重复dfs，之间把已经记录的答案返回即可。
超过k次的就返回0.

代码：

#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include "_my_utils.h" 
#endif#define int long long
#define new _MY_NEW_
#define lg(ITEM) = static_cast<int>(std::log2(ITEM));using namespace std;
using ll = long long;
using PII = std::pair<int, int>;constexpr long long INF = 2E18 + 10;
constexpr int N = 2E6 + 10;void SINGLE_TEST() 
{int le,ri,k;cin>>le>>ri>>k;int L=1,R=ri-le+1;map<array<int,3>,int> ans;function<int(int,int,int)> dfs=[&](int l,int r,int cnt)->int{// if(l==r){//     return 1;// }if(l>r){return 0LL;}if(cnt>k || cnt>70){return 0LL;}if(ans.count({l,r,cnt})){return ans[{l,r,cnt}];}int mid=(l+r)/2;ans[{l,r,cnt}]=dfs(mid+1-mid,r-mid,cnt)+dfs(l,mid-1,cnt+1)+1;// ans[{l,r}]=dfs(l,mid-1,cnt)+dfs(l,mid-1,cnt+1)+1;return ans[{l,r,cnt}];};cout<<dfs(L,R,0)<<"\n";
}signed main(){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int SAMPLES = 1;cin >> SAMPLES;for(int CUR=1;CUR<=SAMPLES;CUR++){SINGLE_TEST();}
}

题意：
给定n个顶点，m条边的图。
每一次从这个图中删除一个最小生成树。知道图不连通。
边权按顺序给出。
问每条边是第几次删除的，假如最后没有删除就输出-1.

题解：
最多有$\frac{m}{n-1}$个最小生成树。
我们使用二维并查集来判断第几颗树的节点是否连通。

按顺序遍历每条边$(u,v)$，二分查找到最小而且没有连通的最小生成树，假如没有就是-1.
二分查找，假如两个节点在第mid颗树$(u,v)$已经连通就$l=mid+1$，否则$r=mid$.

代码：

#include <bits/stdc++.h>
//#define int long long
#define PII pair<int,int>
using namespace std;
const int N=3e5+6;
int ll[N],rr[N];
vector<int> p[N];
int ans[N],cnt[N];int find(int cn,int x)
{if(p[cn][x]==x){return x;}else return p[cn][x]=find(cn,p[cn][x]);
}void solve() 
{int n,m;cin >> n >>m;for(int i=1;i<=m;i++){cin>>ll[i]>>rr[i];if(ll[i]>rr[i])swap(ll[i],rr[i]);p[i].clear();ans[i]=0;}p[0].clear();int x=m/(n-1);for(int i=0;i<=x;i++){p[i].push_back(0);for(int j=1;j<=n;j++){p[i].push_back(j);}cnt[i]=0;}for(int i=1;i<=m;i++){int u=ll[i],v=rr[i];int l=-1,r=x,mid;while(r-l>1){mid=(l+r+1)/2;if(find(mid,u)==find(mid,v))l=mid;else r=mid;}if(r<x){int xx=find(r,u);int yy=find(r,v);p[r][yy]=xx;cnt[r]++;}ans[i]=r;}for(int i=1;i<=m;i++){if(ans[i]==x||cnt[ans[i]]!=n-1)cout<<"-1 ";else cout<<ans[i]+1<<' ';}cout<<'\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int T=1; cin>>T;while(T--){solve();}
}

这篇关于2024杭电8的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---