国外域名拍卖网站,太原做网站公司5大建站服务,中国手机最好的网站排名,网站还建设 域名可以备案吗文章目录 1 十二生肖基本思路#xff1a; 2 欢迎参加福建省大学生程序设计竞赛基本思路#xff1a;代码#xff1a; 3 匹配二元组的数量基本思路#xff1a;代码: 4 元素交换基本思路#xff1a;代码#xff1a; 5 下棋的贝贝基本思路#xff1a;代码#xff1a; 6 方程… 文章目录 1 十二生肖基本思路 2 欢迎参加福建省大学生程序设计竞赛基本思路代码 3 匹配二元组的数量基本思路代码: 4 元素交换基本思路代码 5 下棋的贝贝基本思路代码 6 方程思路代码 1 十二生肖
基本思路
签到题! 龙 - 5
2 欢迎参加福建省大学生程序设计竞赛
基本思路
一道排序的题先按题数排序题树相等时按罚时排序
代码
#includebits/stdc.h
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl \n
#define int long long
const int N 1e610, INF1e1810;
struct Node{int x,y;
};
vectorNode a;
bool cmp(Node xx,Node yy){if(xx.x!yy.x)return xx.xyy.x;return xx.yyy.y;
}void solve(){int n; cinn;for(int i1;in;i){int x,y; cinxy;a.push_back({x,y});}sort(a.begin(),a.end(),cmp);int num0,prex-1,prey-1;for(auto i:a){//计算不相同的次数if(i.xprexi.yprey) continue;num;prexi.x; preyi.y;}coutnum;
} signed main(){IOS;int T1;
// cinT;while(T--){solve();}return 0;
}3 匹配二元组的数量
基本思路
一对二元组(i,j)下标需要满足两个条件一个是ij另一个是ai/jaj/i. 对于第二个条件我们不妨变一下形得到aii ajj.每个数的值都乘以它的下标下标从1开始问题就变成了找到有多少个数相等从这些数中任意选出两个组成一个匹配二元组这不就是组合数吗答案加上每个数个数的C(n,2)可以用哈希统计每个数有多少个
代码:
#includebits/stdc.h
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl \n
#define int long long
const int N 1e610, INF1e1810;
unordered_mapint,int mp;
int n,ans;void solve(){cinn;vectorint a(n1);for(int i1;in;i)cina[i],mp[i*a[i]];for(auto i:mp)ansi.se*(i.se-1)/2;coutans;} signed main(){IOS;int T1;
// cinT;while(T--){solve();}return 0;
}4 元素交换
基本思路
2*N的二进制数组其中0、1的个数各占一半要求交换任意两个元素使得最后的数组不存在连续的0或1我们可以发现最后数组只可能有两种状态一个状态是010101…01另一个状态是101010…10我们只需统计当前数组与目标数组(目标数组为以上两种状态中的一种)有多少个不同的元素假设有x个不同的元素那么x/2即为操作次数为什么呢因为每交换一次就有两个元素回到正确的位置。最后我们只需取两种情况中的最小值即为最小操作次数
代码
#includebits/stdc.h
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl \n
#define int long long
const int N 1e610, INF1e1810;
unordered_mapint,int mp;
int ans0;void solve(){int n;cinn;vectorint a(2*n1),b(2*n1),c(2*n1);for(int i1;i2*n;i){b[i]0,c[i]0;}for(int i1;i2*n;i)cina[i];for(int i1;i2*n;i)//构造两个目标数组其实也可以不用实现判断奇偶即可if(i1) b[i]1;else c[i]1;
// for(int i1;i2*n;i) coutb[i] ;coutendl;
// for(int i1;i2*n;i) coutc[i] ;coutendl;int ansINF,n10,n20;for(int i1;i2*n;i){if(a[i]!b[i]) n1;if(a[i]!c[i]) n2;}coutmin(n1/2,n2/2);
} signed main(){IOS;int T1;
// cinT;while(T--){solve();}return 0;
}5 下棋的贝贝
基本思路
首先我们需要理解题意两个点坐标的曼哈顿距离等于1这两点就是邻居求出所有棋子邻居数量总和的最大值是多少画图的可能会更直观些有图可以发现我们更倾向于构造正方形这样能才能保证邻居数量总和最大每个棋子的最多的邻居是4个即上下左右都是邻居。还可以发现处于边界位置的方块可能有一个邻居两个邻居或者三个邻居。我们不妨假设每个棋子都有4个邻居那么所有棋子邻居数量总和就为4n,然后在减去每个棋子多出来的邻居由图不难发现只有处于边界的棋子的邻居数量是少于4的。我们知道如果是完整的矩形位于矩形四个角的棋子会有2个邻居其余处于边界的棋子都有3个邻居。我们可以把缺的部分补成一个矩形那么多出来的邻居总数矩形的长2矩形的宽2。结合示意图模拟一下不难发现补出来的的棋子不会对多出的邻居总数产生影响。
代码
void solve(){int n; cinn;int l,h,m;msqrt(n);//可以拼凑出的最大的正方形的边长 lhm;if(l*hn) l;//矩形长 if(l*hn) h;//矩形宽 cout4*n-2*l-2*h;
} 6 方程
思路
我们直到了x1/x k, 求 x^(n) 1/(x^n)我们不妨设f(n) x^(n) 1/(x^n) 是关于x的函数以下我粗糙的证明了一下递推公式 我们虽然找到了递推公式但是发现n,k的范围都是1e9直接一项一项求的话肯定会超时的这时我们就需要矩阵快速幂来优化f(1)k , f(2)k*k-2; 构建矩阵第一行(0-1) 第二行1k推得f(2),f(3)
代码
#includebits/stdc.h
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl \n
#define int long long
const int N 2e210, p1e97;
int n2,f[N1],a[N1][N1];void aa(){//a*a long long w[N1][N1];//临时存放a*a memset(w,0,sizeof(w));for(int i1;in;i)for(int k1;kn;k)if(a[i][k])//优化a[i][k]不为0 for(int j1;jn;j)if(a[k][j])//优化 w[i][j]a[i][k]*a[k][j],w[i][j]%p;memcpy(a,w,sizeof(a));//放回a
}void fa(){//f*aint w[N1];memset(w,0,sizeof(w));for(int i1;in;i)for(int j1;jn;j)w[i]f[j]*a[j][i],w[i]%p;memcpy(f,w,sizeof(f));
}void matrixpow(int k){//矩阵快速幂 while(k){if(k1) fa();//f*a;aa();//a*a;k1;}
}void solve(){int m,k;cinmk;f[1]k,f[2]((k*k-2)%pp)%p;//f[1],f[2] A^(m-1) f[m] f[m1]a[1][1]0,a[1][2]-1;//构建矩阵A a[2][1]1,a[2][2]k;matrixpow(m-1);//移m-1位 coutf[1]endl;//f[1]存的即为第m项
} signed main(){
// IOS;int T1;cinT;while(T--){solve();}return 0;
}
/*
1
2 22
*/
