那个网站可以兼职做效果图,网站怎样改logo,wordpress中医主题,主播网站建设A - 无线网络整点栅格统计
题目链接
算法:模拟
题目大意
给你一个n*m的网格,然后输出每一个点作为顶点能构成的正方形数量(可以为斜正方形).
算法思路
本身题目数据是很小的,可以通过n^2的时间复杂度枚举每一个顶点,然后再通过n平方的时间复杂度枚举出另一个对角顶点,判断…A - 无线网络整点栅格统计
题目链接
算法:模拟
题目大意
给你一个n*m的网格,然后输出每一个点作为顶点能构成的正方形数量(可以为斜正方形).
算法思路
本身题目数据是很小的,可以通过n^2的时间复杂度枚举每一个顶点,然后再通过n平方的时间复杂度枚举出另一个对角顶点,判断剩下的两个点是否在网格里面即可.这样的话时间复杂度是n的四次方时间复杂度了,可以通过. 我们可以知道当以A为顶点的斜正方形一定可以被过A的正正方形包围,那么我们每个店只需要求出过这个点所能构成的正正方形数量即可. 至于如何求每个点构成的正正方形数量可以根据个人理解来求. 我的思路是:我们可以通过记录A点左边,上边,斜左上角,本身的正正方形数量,然后这样过A点的正正方形数量就是四个之和.
代码
#includebits/stdc.h
#define ll long long
const int N 1e57;
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(n1-x,m1-y);
}
int celf(int x,int y) {return min(x-1,m1-1)*min(y-1,n1-1);
}
int ti[107][107];
int tj[107][107];
void slove() {for(int i1; i100; i) {ti[0][i]-2;tj[i][0]-2;}cinnm;for(int i1; i(ll)ceil(1.0*(n1)/2); i) {for(int j1; j(ll)ceil(1.0*(m1)/2); j) {a[i][j].ctce(i,j);if(im1) {ti[i][j]ti[i-1][j]1;if(i!1) a[i][j].fra[i-1][j].ctmax(0,(a[i-1][j].fr-ti[i][j]));} else {//需要去掉刚好到i-1的情况a[i][j].fra[i-1][j].fr;}if(jn1) {tj[i][j]tj[i][j-1]1;if(j!1) a[i][j].lta[i][j-1].ctmax(0,(a[i][j-1].lt-tj[i][j]));} else {//需要去掉刚好到j-1的情况a[i][j].lta[i][j-1].lt;}a[i][j].lfcelf(i,j);}}for(int i1; i(ll)ceil(1.0*(n1)/2); i) {for(int j1; j(ll)ceil(1.0*(m1)/2); j) {couta[i][j].cta[i][j].fra[i][j].lta[i][j].lf ;}if((m1)%20) {for(int j(ll)ceil(1.0*(m1)/2); j1; --j) {couta[i][j].cta[i][j].fra[i][j].lta[i][j].lf ;}} else {for(int j(ll)ceil(1.0*(m1)/2)-1; j1; --j) {couta[i][j].cta[i][j].fra[i][j].lta[i][j].lf ;}}coutendl;}if((n1)%20) {for(int i(ll)ceil(1.0*(n1)/2); i1; --i) {for(int j1; j(ll)ceil(1.0*(m1)/2); j) {couta[i][j].cta[i][j].fra[i][j].lta[i][j].lf ;}if((m1)%20) {for(int j(ll)ceil(1.0*(m1)/2); j1; --j) {couta[i][j].cta[i][j].fra[i][j].lta[i][j].lf ;}} else {for(int j(ll)ceil(1.0*(m1)/2)-1; j1; --j) {couta[i][j].cta[i][j].fra[i][j].lta[i][j].lf ;}}coutendl;}} else {for(int i(ll)ceil(1.0*(n1)/2)-1; i1; --i) {for(int j1; j(ll)ceil(1.0*(m1)/2); j) {couta[i][j].cta[i][j].fra[i][j].lta[i][j].lf ;}if((m1)%20) {for(int j(ll)ceil(1.0*(m1)/2); j1; --j) {couta[i][j].cta[i][j].fra[i][j].lta[i][j].lf ;}} else {for(int j(ll)ceil(1.0*(m1)/2)-1; j1; --j) {couta[i][j].cta[i][j].fra[i][j].lta[i][j].lf ;}}coutendl;}}return;
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t 1;
// cint;while(t--) {slove();coutendl;}return 0;
}
C. Liar
题目链接
算法:思维
题目大意
有n个数,这些个数的总和为s,这些数有真有假,输出最多有多少个数是真的
算法思路
因为当这个数为假的时候,我们可以把这个数设为无穷数,那么当n个数都为真无法满足总和为s的情况,我们可以让前n-1个数都为真,然后通过最后一个数进行调节,满足n个数的总和为s的情况
代码
#includebits/stdc.h
#define ll long long
const int N 1e57;
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;cinns;for(int i1; in; i) cina[i];sort(a1,an1);ll ans 0;for(int i1; in; i) {ansa[i];}if(anss) {coutn;return;}coutn-1;
}
int main() {int t 1;
// cint;while(t--) {slove();coutendl;}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
#includebits/stdc.h
#define ll long long
const int N 1e67;
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 {mapint,ll mp;setint st;
};
Node a[N];
priority_queuell, vectorll, lessll q[N];
setint tst;
ll q_pow(ll n,ll x) {ll sum1;while(x) {if(x1) sum*n;x1;n*n;n%M;sum%M;}sum%M;return sum;
}
void slove() {ll n;cinn;for(int i1,t; in; i) {cint;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;}coutansn-sz;return;
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);a[1].mp[1]1;for(int i2; i1e6; i) {int flag 0;for(int j2; j*ji; j) {if(i%j0) {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 i1;i1e6;i) {
// mx max(mx,(int)a[i].st.size());
// }
// coutmx;int t 1;cint;while(t--) {slove();coutendl;}return 0;
}这个代码部分main里面对如何在nlogn的时间复杂度求出1-n里面每个数分别有哪些因子可以重点看一下.
