2022杭电第八场

1004 Quel'Thalas

题意：

问最少需要画多少条不过原点的直线，能经过第一象限中（0，0）到（n,n）这个正方形上除（0，0）的所有的点。

思路：

作 2 n条$x+y=bx\; +\; y\; =\; b$的直线即可。故答案为 2n。

代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		printf("%d\n",2*n);
	}
    return 0;
}

1001 Theramore

题意：

有一串01序列，可以任意次地选择一个长度为奇的区间，并把它给翻转过来。使得序列的字典序最小。输出这个字典序最小的序列。

思路：

奇数上的0或1只能翻转到奇数位上，记录有多少1在奇数位，有多少1在偶数位。从后往前填1，1不够填只能填0。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int t;
char s[N],st[N];
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0); 
	cout.tie(0);
	scanf("%d",&t);
	while(t--){	
		memset(s, 0, sizeof(s)); 
		memset(st, 0, sizeof(st)); 
		scanf("%s",&s);
		int len=strlen(s);
		int od=0,ev=0,z=0;
		for(int i=0;i<len;i++){
			if(s[i]=='1'&&i%2==0) ev++;
			else if(s[i]=='1'&&i%2!=0) od++;
		}
		for(int i=len-1;i>=0;i--){
			if(i%2==0){
				if(ev>0) {
					st[i]='1';
					ev--;
				}
				else st[i]='0';
			}
			else {
				if(od>0){
					st[i]='1';
					od--;
				}
				else st[i]='0';
			}
		}
	printf("%s\n",st);
		
		
	}
	
}

1011 Stormwind

题意：

给定 n × m 的矩形，只能水平切和竖直切，切尽可能多刀使得每块子矩形的面积均大于等于k，问最多切多少刀。

思路：

从1到$\sqrt{(}k)\backslash sqrt(k)$枚举子矩阵长度$xx$，那么另一个方向上的间隔就是$\lceil (\frac{k}{x})\rceil \backslash lceil(\backslash frac\{k\}x)\; \backslash rceil$，得到了两方向的间隔后就可以算出来画线数了，若间隔为x，那么这个方向上的画线数就是$\lfloor (n\mathrm{/}x)-1\rfloor \backslash lfloor(n/x)-1\backslash rfloor$，floor表示下取整，两方向统计出来加和就是答案。

代码：

#include <bits/stdc++.h>
using namespace std;

signed main(){
	int T;
	cin >> T;
	while(T--){
		int n, m, k;
		cin >> n >> m >> k;
		int ans = 0;
		for(int i = 1; i <=sqrt(k); i++){
			int res = floor(1.0*n/i)-1;
			int t = ceil(1.0*k/i);
			if(t > m) continue;
			res += floor(1.0*m/t)-1;
			ans = max(ans, res);
		}
		cout << ans << endl;
	}
}