2024/8/8训练

A - 无线网络整点栅格统计

题目链接

算法:模拟

题目大意

给你一个n*m的网格,然后输出每一个点作为顶点能构成的正方形数量(可以为斜正方形).

算法思路

本身题目数据是很小的,可以通过n^2的时间复杂度枚举每一个顶点,然后再通过n平方的时间复杂度枚举出另一个对角顶点,判断剩下的两个点是否在网格里面即可.这样的话时间复杂度是n的四次方时间复杂度了,可以通过.
我们可以知道当以A为顶点的斜正方形一定可以被过A的正正方形包围,那么我们每个店只需要求出过这个点所能构成的正正方形数量即可.
至于如何求每个点构成的正正方形数量可以根据个人理解来求.
我的思路是:我们可以通过记录A点左边,上边,斜左上角,本身的正正方形数量,然后这样过A点的正正方形数量就是四个之和.

代码

#include<bits/stdc++.h>
#define ll long long
const int N = 1e5+7;
int dx[]= {1,-1,0,0,1,1,-1,-1};
int dy[]= {0,0,1,-1,1,-1,1,-1};
using namespace std;
struct Node {//自身 左边 上边//左上角int ct,lt,fr;int lf;
};
Node a[107][107];
int n,m;
int ce(int x,int y) {return min(n+1-x,m+1-y);
}
int celf(int x,int y) {return min(x-1,m+1-1)*min(y-1,n+1-1);
}
int ti[107][107];
int tj[107][107];
void slove() {for(int i=1; i<=100; ++i) {ti[0][i]=-2;tj[i][0]=-2;}cin>>n>>m;for(int i=1; i<=(ll)ceil(1.0*(n+1)/2); ++i) {for(int j=1; j<=(ll)ceil(1.0*(m+1)/2); ++j) {a[i][j].ct=ce(i,j);if(i<=m+1) {ti[i][j]=ti[i-1][j]+1;if(i!=1) a[i][j].fr=a[i-1][j].ct+max(0,(a[i-1][j].fr+-ti[i][j]));} else {//需要去掉刚好到i-1的情况a[i][j].fr=a[i-1][j].fr;}if(j<=n+1) {tj[i][j]=tj[i][j-1]+1;if(j!=1) a[i][j].lt=a[i][j-1].ct+max(0,(a[i][j-1].lt+-tj[i][j]));} else {//需要去掉刚好到j-1的情况a[i][j].lt=a[i][j-1].lt;}a[i][j].lf=celf(i,j);}}for(int i=1; i<=(ll)ceil(1.0*(n+1)/2); ++i) {for(int j=1; j<=(ll)ceil(1.0*(m+1)/2); ++j) {cout<<a[i][j].ct+a[i][j].fr+a[i][j].lt+a[i][j].lf<<" ";}if((m+1)%2==0) {for(int j=(ll)ceil(1.0*(m+1)/2); j>=1; --j) {cout<<a[i][j].ct+a[i][j].fr+a[i][j].lt+a[i][j].lf<<" ";}} else {for(int j=(ll)ceil(1.0*(m+1)/2)-1; j>=1; --j) {cout<<a[i][j].ct+a[i][j].fr+a[i][j].lt+a[i][j].lf<<" ";}}cout<<endl;}if((n+1)%2==0) {for(int i=(ll)ceil(1.0*(n+1)/2); i>=1; --i) {for(int j=1; j<=(ll)ceil(1.0*(m+1)/2); ++j) {cout<<a[i][j].ct+a[i][j].fr+a[i][j].lt+a[i][j].lf<<" ";}if((m+1)%2==0) {for(int j=(ll)ceil(1.0*(m+1)/2); j>=1; --j) {cout<<a[i][j].ct+a[i][j].fr+a[i][j].lt+a[i][j].lf<<" ";}} else {for(int j=(ll)ceil(1.0*(m+1)/2)-1; j>=1; --j) {cout<<a[i][j].ct+a[i][j].fr+a[i][j].lt+a[i][j].lf<<" ";}}cout<<endl;}} else {for(int i=(ll)ceil(1.0*(n+1)/2)-1; i>=1; --i) {for(int j=1; j<=(ll)ceil(1.0*(m+1)/2); ++j) {cout<<a[i][j].ct+a[i][j].fr+a[i][j].lt+a[i][j].lf<<" ";}if((m+1)%2==0) {for(int j=(ll)ceil(1.0*(m+1)/2); j>=1; --j) {cout<<a[i][j].ct+a[i][j].fr+a[i][j].lt+a[i][j].lf<<" ";}} else {for(int j=(ll)ceil(1.0*(m+1)/2)-1; j>=1; --j) {cout<<a[i][j].ct+a[i][j].fr+a[i][j].lt+a[i][j].lf<<" ";}}cout<<endl;}}return;
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;
//	cin>>t;while(t--) {slove();cout<<endl;}return 0;
}

C. Liar

题目链接

算法:思维

题目大意

有n个数,这些个数的总和为s,这些数有真有假,输出最多有多少个数是真的

算法思路

因为当这个数为假的时候,我们可以把这个数设为无穷数,那么当n个数都为真无法满足总和为s的情况,我们可以让前n-1个数都为真,然后通过最后一个数进行调节,满足n个数的总和为s的情况

代码

#include<bits/stdc++.h>
#define ll long long
const int N = 1e5+7;
int dx[]= {1,-1,0,0,1,1,-1,-1};
int dy[]= {0,0,1,-1,1,-1,1,-1};
using namespace std;
ll a[N];
void slove() {ll n,s;cin>>n>>s;for(int i=1; i<=n; ++i) cin>>a[i];sort(a+1,a+n+1);ll ans = 0;for(int i=1; i<=n; ++i) {ans+=a[i];}if(ans==s) {cout<<n;return;}cout<<n-1;
}
int main() {int t = 1;
//	cin>>t;while(t--) {slove();cout<<endl;}return 0;
}

Magic LCM

题目链接

算法:数学+模拟+贪心

题目大意

给你一个长度为n的数组,然后你可以进行无数次操作:选择两个不同的数(x,y),设x为gcd(x,y),y为lcm(x,y).
求出最后这个数组之和的最大值.

算法思路

对于两个数进行gcd和lcm赋值,其实gcd就是公共因子,lcm就是公共因子不同的因子.
而且因子和因子之间互不打扰.
那么我们就可以把数组里面的每一个数进行拆解,拆解成质因子,依次求出进行操作以后的最大值.
又因为操作就是将公共因子乘不同的因子,那么我们可以让质因子个数多的先提供,求出一个当前的最大值.
比如:9 6 4 27 10 12这个数组
9->33
6->23
4->22
27->333
10->25
12->223
那么我们可以先让4提供两个2,27提供三个3,10提供一个5,这样组成540.
剩下的数
33
23
2
22*3
注意,质因子之间相互独立,所以不用在意是具体是谁提供的
我们继续两个2,两个3组成36
一个2.一个3
组成6
一个2.一个3
组成6
这样把所有的质因子都用掉以后
还剩下两个数,这两个数就是1

#include<bits/stdc++.h>
#define ll long long
const int N = 1e6+7;
const int M = 998244353;
int dx[]= {1,-1,0,0,1,1,-1,-1};
int dy[]= {0,0,1,-1,1,-1,1,-1};
using namespace std;
struct Node {map<int,ll> mp;set<int> st;
};
Node a[N];
priority_queue<ll, vector<ll>, less<ll>> q[N];
set<int> tst;
ll q_pow(ll n,ll x) {ll sum=1;while(x) {if(x&1) sum*=n;x>>=1;n*=n;n%=M;sum%=M;}sum%=M;return sum;
}
void slove() {ll n;cin>>n;for(int i=1,t; i<=n; ++i) {cin>>t;for(auto &v:a[t].st) {tst.insert(v);q[v].push(a[t].mp[v]);}}ll ans = 0;int sz = 0;int flag = 0;while(1) {flag = 0;ll tans = 1;for(auto it = tst.begin(); it != tst.end();) {if(q[*it].empty()) {it = tst.erase(it);} else {flag = 1;ll t = q_pow(*it,q[*it].top());q[*it].pop();tans*=t;tans%=M;++it;}}ans += tans;ans%=M;sz++;if(flag == 0) break;}cout<<ans+n-sz;return;
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);a[1].mp[1]=1;for(int i=2; i<=1e6; ++i) {int flag = 0;for(int j=2; j*j<=i; ++j) {if(i%j==0) {flag = 1;int t = i/j;for(auto &v:a[t].st) {a[i].mp[v]+=a[t].mp[v];a[i].st.insert(v);}a[i].mp[j]++;a[i].st.insert(j);break;}}if(flag == 0) {a[i].mp[i]++;a[i].st.insert(i);}}//	int mx = 0;
//	for(int i=1;i<=1e6;++i) {
//		mx = max(mx,(int)a[i].st.size());
//	}
//	cout<<mx;int t = 1;cin>>t;while(t--) {slove();cout<<endl;}return 0;
}

这个代码部分main里面对如何在nlogn的时间复杂度求出1-n里面每个数分别有哪些因子可以重点看一下.