A.Maximum Square
B1.Character Swap (Easy Version)
B2.Character Swap (Hard Version)
C.Tile Painting
D.0-1 MST
A.Maximum Square
题目类型:数学【?】
题目链接:A题链接
题目大意:给你n条长度为a[i]的木棍,宽度为1的木棍,询问你如何排列能获得一个边最大的正方形
通过图我们能很好的理解题目的意思
解题思路:只需要排一下序,按从高到低去排序,每拼上一条宽度是增加1的,如果你的最小高度无法匹配你的总宽度的话就要跳出了,以此来寻找最大边长
/** * This code has been written by YueGuang, feel free to ask me question. Blog: http://www.yx.telstudy.xyz * created: */
#include <cstdio>
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#define REP(i, a, b) for(int i = a; i < b; i++)
#define REP_(i, a, b) for(int i = a; i <= b; i++)
#define sl(n) scanf("%lld", &n);
#define si(n) scanf("%d", &n);
#define RepAll(a) for(auto x: a)
#define cout(ans) cout << ans << endl;
typedef long long ll;
using namespace std;
bool cmp(int a, int b){return a > b;}
const int maxn = 2000;
int a[maxn];
int main(){
//freopen("in.txt", "r", stdin);
int k, n; scanf("%d", &k);
while(k--){
scanf("%d", &n);
for(int i = 0; i < n; i++){scanf("%d", &a[i]);}
sort(a, a+n, cmp);
int j = 1;
for(int i = 0; i < n; j++, i++){
if(a[i] < j){break;}
}
printf("%d\n", j-1);
}
}
B1.Character Swap (Easy Version)
题目类型:模拟
题目链接:B1题链接
题目大意:给你两个长度为n的字符串,分别为s和t,让你交换一次ti和sj使得两个字符串相同,问是否能做到,如果可以就输出YES不行就输出NO
这句话听关键的,特意复制下来
Since Ujan is lazy, he will perform the following operation exactly once: he takes two positions i and j (1≤i,j≤n, the values i and j can be equal or different), and swaps the characters si and tj.
解题思路:寻找s中第一个与t不一样的字符,然后再寻找t中第二个与s不一样的字符,交换后比较
/** * This code has been written by YueGuang, feel free to ask me question. Blog: http://www.yx.telstudy.xyz * created: */
#include <cstdio>
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#define REP(i, a, b) for(int i = a; i < b; i++)
#define REP_(i, a, b) for(int i = a; i <= b; i++)
#define sl(n) scanf("%lld", &n);
#define si(n) scanf("%d", &n);
#define RepAll(a) for(auto x: a)
#define cout(ans) cout << ans << endl;
typedef long long ll;
using namespace std;
string s, t;
//char s[1010], t[1010];
//map<char, int> f;
int main(){
//freopen("in.txt", "r", stdin);
int q, n; scanf("%d", &q);
while(q--){
int cnt = 0;
scanf("%d", &n);
cin >> s >> t;
//char a[];
int flag = -1;
for(int i = 0; i < n; i++){
if(s[i]!=t[i] && flag == -1){
//cout << "now : "<<flag << endl;
flag = i; continue;}
if(s[i]!=t[i] && flag >= 0 ){
//cout<< flag << '\n';
char tmp = t[i];
t[i] = s[flag];
s[flag] = tmp;
break;
}
}
//cout << s << " " << t << '\n';
if (s==t) printf("Yes\n");
else printf("No\n");
}
}
B2.Character Swap (Hard Version)
题目类型:
题目链接:
下次一定补
C. Tile Painting
题目类型:数学
题目链接:C题链接
题目大意:给你 n块边长为1的方块,对方快进行涂色,如果满足要求 |i - j| > 1 且 n mod |i - j| == 0 则第i个方块和第j个方块要求涂上相同的颜色,求解需要多少种颜色
左图:输入的n为4
i = 4, j = 2 满足所以2,4相同颜***r> 同理1,3满足, 所以1,3同色,而1,2或3,4无法满足所以1,2,3,4不能同色,综上需要使用两种颜色
解题思路:
(1)当看到n mod |i-j| = 0的时候,思路应该向公因数靠拢,因为当i 和 j 能够满足这条件的时候i和j的差值一定是n的公因数
(2)也可以考虑一下素数,因为输入的n是素数的话,n的因子只有本身和1,那就只能输出n了,每种色块都要是不相同的
/* *这个是想暴力找规律的一段代码 */
#include <cstdio>
#include <iostream>
using namespace std;
int main(){
int n; scanf("%d", &n);
for(int i = 1; i <= n; i++){
printf("%d\n", i);
for(int j = 1; j <= n; j++){
if (abs(i-j) > 1 && n % (i-j) == 0){
printf("%d ", j);
}
}
cout << '\n';
}
}
能够验证,素数无可选因子
那么非素数,我们拿样例 n = 4测试一下
i = 1
j = 3
i = 2
j = 4
i = 3
j = 1
i = 4
j = 2
- 可以的到这么几组数据,没错就是1、3共色,2、4共色
- 循环不需要完全遍历n,只需要sqrt(n)就可以了,可以转化为数 i * i <= n 就可以了
/** * This code has been written by YueGuang, feel free to ask me question. Blog: http://www.yx.telstudy.xyz * created: */
#include <cstdio>
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#define REP(i, a, b) for(int i = a; i < b; i++)
#define REP_(i, a, b) for(int i = a; i <= b; i++)
#define sl(n) scanf("%lld", &n);
#define si(n) scanf("%d", &n);
#define RepAll(a) for(auto x: a)
#define cout(ans) cout << ans << endl;
typedef long long ll;
using namespace std;
inline ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a%b);}
int main(){
ll n; scanf("%lld", &n);
ll d = n;
for(ll i = 2; i * i <= n; i++){
if (n % i == 0){
d = gcd(i ,d);
d = gcd(d, n/i);
}
}
printf("%lld\n", d);
}