专栏文章

2025寒假专场1

ccompaq
题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqksbnz
此快照首次捕获于
2025/12/04 06:25
3 个月前
此快照最后确认于
2025/12/04 06:25
3 个月前
查看原文
101相同矩阵
因为可以上移，左移，所以对于每一行的字符串都复制一遍，然后接到后面，然后再垂直复制一遍。
也就是原来字符串的大小是hh行ww列，现在是2h×2w2h \times 2w
答案就在这个2h×2w2h \times 2w中能否找到B字符串即可，数据范围较小，直接暴力匹配，时间复杂度为h2×w2h^2 \times w^2
CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 100;

string a[N], b[N], mycp[N];
int h, w;

bool check(int x, int y){
	for(int i = 1; i <= h; i++){
		if(mycp[x].substr(y, w) == b[i]){
			x++;
			if(x > 2 * h) return false;
		}
		else
			return false;
	}
	return true;
}

int main(){

    cin >> h >> w;
    
    for(int i = 1; i <= h; i++) cin >> a[i];
    
    for(int i = 1; i <= h; i++) cin >> b[i];
    
    for(int i = 1; i <= h; i++) mycp[i] = a[i] + a[i];
   
    for(int i = h + 1; i <= h + h; i++) mycp[i] = mycp[i - h];
	
	for(int i = 1; i <= h + h; i++){
		for(int j = 0; j < 2 * w; j++){
			if(j + w - 1 > 2 * w) break;
			if(check(i, j)){
				puts("Yes");
				return 0;
			}
		}
	}
    puts("No");
    return 0;
}
102交叉
枚举每个'#'，然后进行X扩展即可
CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;

int h, w;
char c[N][N];
int s[N];

int main(){
	cin >> h >> w;
	
	for (int i = 1; i <= h; i ++)
		for (int j = 1; j <= w; j ++)
			cin >> c[i][j];
			
	for (int i = 2; i < h; i ++)
		for (int j = 2; j < w; j ++)
			if (c[i][j] == '#'){
				int deep = 0;
				while (i + deep + 1 <= h && i - deep + 1 >= 1 && 
				j - deep + 1 >= 1 && j + deep + 1 <= w && 
				c[i + deep + 1][j - deep - 1] == '#' && 
				c[i + deep + 1][j + deep + 1] == '#' && 
				c[i - deep - 1][j - deep - 1] == '#' && 
				c[i - deep - 1][j + deep + 1] == '#')
					deep ++;
				s[deep] ++;
			}
	
	for (int i = 1; i <= min(h, w); i ++)
		cout << s[i] << " ";
		
	return 0;
}
/*
枚举每一个 # ,进行X扩展即可，注意边界 
*/
103AABCC
筛选出质数范围：因为N≤1012N \leq 10^{12}, 所以筛出10610^6以内的质数。
根据条件，a5≤Na^5 \leq N ,则aa是不超过300300的质数。 再根据条件范围枚举即可。
CPP
#include <bits/stdc++.h>

#define int long long 

using namespace std;

const int  N = 1e6 + 10;

int n;
vector<int> prime;
bool st[N];

void div(int x){
    for (int i = 2; i <= x; i ++){
        if (!st[i]) prime.push_back(i);
        for (int j = 0; prime[j] <= x / i; j ++){
            st[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

signed main(){
	cin >> n;	
	
	div(N);
	
	//cout << prime.size() << endl;
	int res = 0;
	for (int i = 0; i < 62; i ++)
		for (int j = i + 1; prime[i] * prime[j] * prime[j] * prime[i] * prime[j] <= n; j ++)
			for (int k = j + 1; prime[i] * prime[j] * prime[k] * prime[i] * prime[k] <= n; k ++)
				res ++;
					
	cout << res << endl;
	return 0;
}
104更多的假期
假设原S中的'x'的数量为pp，若k>pk > p，则需要k/pk/p个完整的SS，剩余的k%pk \% p个'x'的数量，一部分在最前面的一段SS中，一部分在最后一段的SS中。
枚举在最前面的SS的开始位置LL, 再二分枚举最后一段中结束的位置RR。
注意计算[L, R]之间的‘x’的数量。
时间复杂度为nlog(n∗m)nlog(n*m)
CPP
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 3e5 + 10;

int n, m, k, p;
int f[N], r[N];
string s;

bool check(int L, int R){
	int cnt;
	if(R <= n) cnt = f[R] - f[L - 1];
	else cnt = r[L] + f[R % n] + (R - n) / n * p; // R比你大的话，则第一段的个数，最后一段的个数，再加上中间的个数 
	return cnt <= k;
}

signed main(){
	
	cin >> n >> m >> k >> s;

	s = ' ' + s;
	for (int i = 1; i <= n; i ++)
		f[i] = f[i - 1] + (s[i] == 'x'), p += (s[i] == 'x');
		
	for (int i = n; i >= 1; i --)
		r[i] = r[i + 1] + (s[i] == 'x');
		
	int res = 0, ans = 0;
	for (int i = 1; i <= n; i ++){
		int  L = i, R = n * m;
		while (L <= R){
			int mid = (L + R) / 2;
			if (check(i, mid)) ans = mid, L = mid + 1; // 从i开始的，到mid这段区间内x的数量 
			else R = mid - 1;
		}
		res = max(res, ans - i + 1);
	}
	
	cout << res << endl;
	return 0;
}
105P-smoonth数
100100以内的质数，分成两组，生成两个集合，每个集合内部生成含该质因子的所有数，这样生成的两个集合内部数量，尽可能一样多。
枚举第一个集合的数值xx，二分枚举第二个集合中第一个比n/xn / x大的数的位置，则前面位置上的数都是能贡献答案。
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int pri[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 
					37, 41, 43, 47, 53, 59, 61, 67, 71, 
					73, 79, 83, 89, 97};
const int p1[] = {0, 2, 3, 5, 7, 11, 13, 17};
const int p2[] = {0, 19, 23, 29, 31, 37, 41, 43, 47,
				 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
const int P1 = 7, P2 = 18;
int n, p;
vector <int> v1, v2;

void dfs1(int x, int now){
    v1.push_back(x);
    for(int i = now; i <= P1; i++)
        if(x * p1[i] <= n && p1[i] <= p)
            dfs1(x * p1[i], i);
}

void dfs2(int x, int now){
    v2.push_back(x);
    for(int i = now; i <= P2; i++)
        if(x * p2[i] <= n && p2[i] <= p)
            dfs2(x * p2[i], i);
}

int ans;

signed main(){
    cin >> n >> p;
    dfs1(1, 1);
    dfs2(1, 1);
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    //cout << v1.size() << " " << v2.size() << "\n";
	for(int i = 0; i < v1.size(); i++){
		int res = upper_bound(v2.begin(), v2.end(), n / v1[i]) - v2.begin();
		ans += res;
	}
    cout << ans << "\n";
    return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...