如何创建网站名称,南浔区住房和城乡建设局网站,网站建设公司的选择,贵阳市住房和城乡建设厅网站https://vjudge.net/contest/581947
A - Ultra-QuickSort
题意
每次给n个无序的数#xff0c;互不重复#xff0c;问最少需要多少次必要的交换操作使n个数有序。
思路
看一眼想到逆序数#xff0c;然后验证了逆序数的个数符合样例#xff0c;但想了一个3 2 1的话实际上…https://vjudge.net/contest/581947
A - Ultra-QuickSort
题意
每次给n个无序的数互不重复问最少需要多少次必要的交换操作使n个数有序。
思路
看一眼想到逆序数然后验证了逆序数的个数符合样例但想了一个3 2 1的话实际上只需要交换一次但题意说的是必要交换次数也不一样是最优的交换次数那样就太难了。 于是就简化问题求一个序列逆序数的个数就用归并了上课讲过可以在归并拆分返回的时候进行求逆序对求逆序对两种一种求每个数的右边比它小的数的个数一种求每个数左边比它大的个数我用第二种做的归并返回的时候两个数组都是有序的可以求右边的数组中每个元素对于左边一共有几个比他大的代码能力还行wa了一次因为数组开的int 归并一次就写对了我感觉我又行了哈哈哈。
#includecstring
#includecstdio
#includeiostream
#includecmath
#includealgorithm
using namespace std;const int maxn500005;
long long a[maxn],box[maxn];
long long ans;
void mergesort(int left,int right)
{if(leftright) return;int mid(leftright)/2;mergesort(left,mid);mergesort(mid1,right);int jleft;for(int imid1;iright;i){while(a[j]a[i]jmid){j;} ansansmid-j1;} int ileft;jmid1;int t1;while(imidjright){if(a[i]a[j])box[t]a[i];elsebox[t]a[j];}while(imid)box[t]a[i];while(jright)box[t]a[j];t1;for(int ileft;iright;i)a[i]box[t];
}
int main()
{int n;while(scanf(%d,n)n!0){memset(a,0,sizeof(a));for(int i1;in;i)scanf(%lld,a[i]);ans0;mergesort(1,n);
// for(int i1;in;i)
// printf(%d ,a[i]);
// printf(\n); printf(%lld\n,ans);} return 0;
}
B - Hanoi Tower Troubles Again!
题意
给n个柱子这个人要从第一根柱子到第n个柱子挨个往上面放球球编号从1开始递增要求两个相邻球编号和为完全平方数。
思路
简单模拟题
#includecstring
#includecstdio
#includeiostream
#includecmath
#includealgorithm
using namespace std;int box[55];
int main()
{int T;scanf(%d,T);while(T--){int n;scanf(%d,n);memset(box,0,sizeof(box));int i1;while(1){int flag0;for(int j1; jn; j){if(box[j]0){box[j]i;flag1;break;}else{int k(int)sqrt(box[j]i);if(k*k(box[j]i)){box[j]i;flag1;break;}}}if(flag0) break;}printf(%d\n,i-1);}
}C - Fibonacci Again
思路模拟题
#includebits/stdc.h
using namespace std;const int MAXN1000005;
int f[MAXN];
int main()
{f[0]7;f[1]11;for(int i2;i1000000;i) f[i]f[i-1]%3f[i-2]%3;int t;while(scanf(%d,t)!EOF){if(f[t]%30)printf(yes\n); elseprintf(no\n);}return 0;
}
E - Fire Net
题意
给n*n(n4)的格子格子上可能有墙或者为空地空地可以建设碉堡碉堡可以上下左右射击射不穿墙问最多可以建设多少碉堡
思路
DFS模拟简单题 一共最多16个格子嘛我就是从上往下从左往右挨个尝试每个位置然后对于每个位置能不能安装只需要扫描它的上方和左方是否有碉堡就可以啦注意一下边界就好。
#includecstring
#includecstdio
#includeiostream
#includecmath
#includealgorithm
using namespace std;int m[10][10];
int n;
int ans;
void dfs(int start,int cnt)
{if(startn*n){ansmax(ans,cnt);
// if(cnt4)
// {
// for(int i1; in; i,printf(\n))
// for(int j1; jn; j)
// printf(%d ,m[i][j]);
// printf(\n);
// }return;}int row(start-1)/n1;int col(start-1)%n1;for(int istart; in*n; i){
// 取if(m[row][col]!1){int flag1;for(int jcol-1; j1m[row][j]!1; j--)if(m[row][j]2){flag0;break;}for(int jrow-1; j1m[j][col]!1; j--)if(m[j][col]2){flag0;break;}if(flag){m[row][col]2;dfs(i1,cnt1);m[row][col]0;}}
// 不取dfs(i1,cnt);}return;
}
int main()
{while(scanf(%d,n)n!0){ans0;getchar();for(int i1; in; i){for(int j1; jn; j){char c;scanf(%c,c);if(c.) m[i][j]0;else m[i][j]1;}getchar();}for(int i1; in*n; i){dfs(i,0);}printf(%d\n,ans);}
}
/*
4
.X..
....
XX..
....
*/
G - Maximum Subarray Sum
题意
最大连续子序列和
思路
简单题注意开long long和可能超int
#includecstring
#includecstdio
#includeiostream
#includecmath
#includealgorithm
using namespace std;
const int MAXN2e55;
int a[MAXN];
int main()
{int n;scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]);long long maxx0;long long ansa[1];for(int i1;in;i){maxxmaxxa[i];ansmax(maxx,ans);if(maxx0) maxx0;}printf(%lld,ans);
}J - Beat the Spread!
#includecstring
#includecstdio
#includeiostream
#includecmath
#includealgorithmint main()
{int T;scanf(%d,T);while(T--){int a,b;scanf(%d%d,a,b);if((ab)%2){printf(impossible\n);continue;}int maxx(ab)/2;int minna-maxx;if(maxx0||minn0){printf(impossible\n);continue;}printf(%d %d\n,maxx,minn);}
}
