首页 > 其他分享 >模拟赛记录

模拟赛记录

时间：2023-09-03 14:12:12浏览次数：60  
标签：typedef const 记录 int LL cin long 模拟

23CSP7连测

9.2 day1

260->100+100+5+10=225

C暴力写寄了。

A

tag : 二维前缀和

前缀和记录一下左边和上面跟自己不一样的数量，暴力查询每一个矩形。

code 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 2e3 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, m, h, w, k, res;
int a[N][N], up[N][N], L[N][N];
int sum(int s[][2005], int x1, int y1, int x2, int y2) {
	if(!(x1 <= x2 && y1 <= y2)) return 0;
	return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> m >> h >> w >> k;
	for(int i = 1; i <= n; i ++) {
		string s;
		cin >> s;
		for(int j = 1; j <= m; j ++) {
			a[i][j] = s[j - 1] - '0';
		}
	}
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= m; j ++) {
			if(i != 1) up[i][j] = (a[i][j] != a[i - 1][j]);
			if(j != 1) L[i][j] = (a[i][j] != a[i][j - 1]);
		}
	}
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= m; j ++) {
			up[i][j] += up[i - 1][j] + up[i][j - 1] - up[i - 1][j - 1];
			L[i][j] += L[i - 1][j] + L[i][j - 1] - L[i - 1][j - 1];
		}
	}
	for(int i = 1; i + h - 1 <= n; i ++) {
		for(int j = 1; j + w - 1 <= m; j ++) {
			int ni = i + h - 1, nj = j + w - 1;
			int tot = sum(up, i + 1, j + 1, ni - 1, nj - 1);
			tot += sum(L, i + 1, j + 1, ni - 1, nj - 1);
			tot += sum(up, ni, j + 1, ni, nj - 1);
			tot += sum(L, ni, j + 1, ni, nj - 1);
			tot += sum(up, i + 1, j, ni - 1, j);
			tot += sum(up, i + 1, nj, ni - 1, nj);
			tot += sum(L, i + 1, nj, ni - 1, nj);
			tot += sum(L, i, j + 1, i, nj - 1);
			tot += sum(up, ni, j, ni, j);
			tot += sum(L, i, nj, i, nj);
			tot += sum(up, ni, nj, ni, nj) + sum(L, ni, nj, ni, nj);
			if(tot >= k) res ++;
		}
	}
	cout << res << '\n';
    return 0;
}

B

tag : 我也不知道

乱搞？

code 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
void solve() {
	int n;
	LL sum = 0;
	cin >> n;
	vector<int> a(n);
	int f = 1;
	LL s = 0;
	for(int i = 0; i < n; i ++) {
		cin >> a[i];
	}
	for(int i = n - 1; i >= 0; i --) {
		s += a[i] * f;
		f *= -1;
	}
	if(n % 2 == 0) {
		if(s == 0) cout << 1 << '\n';
		else cout << 0 << '\n';
	}
	else if(s & 1 || s < 0) {
		cout << 0 << '\n';
	}
	else {
		s >>= 1;
		for(int i = 0; i < n; i ++) {
			s = a[i] - s;
			if(s < 0) {
				cout << 0 << '\n';
				return;
			}
		}
		cout << 1 << '\n';
	}
}	
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
	int t;
	cin >> t;
	while(t --) {
		solve();
	}
    return 0;
}

C

tag : 矩阵加速递推

一眼矩阵快速幂，但是系数是会变的赛时没想出来。

模数 2027 比较小， \(f_i，f_{i+2027}\) 的转移矩阵是一样的，可以预处理。

code 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 2027;
LL n;
int m;
int a[20];
struct Matrix {
	int n, m;
	int c[20][20];
	void init(int _n, int _m) {
		n = _n, m = _m;
		for(int i = 1; i <= n; i ++)
			for(int j = 1; j <= m; j ++) c[i][j] = 0;
	}
	Matrix operator *(const Matrix t) const {
		static Matrix res;
		res.init(n, t.m);
		for(int i = 1; i <= res.n; i ++)
			for(int j = 1; j <= res.m; j ++)
				for(int k = 1; k <= m; k ++) {
					res.c[i][j] = (res.c[i][j] + c[i][k] * t.c[k][j]) % mod;
				}
		return res;
	}
} base, ans, cur[N];
Matrix power(Matrix a, LL b) {
	Matrix res;
	res.init(15, 15);
	for(int i = 1; i <= 15; i ++) {
		res.c[i][i] = 1;
	}
	for(; b; a = a * a, b >>= 1) if(b & 1) res = res * a;
	return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> m;
	for(int i = 1; i <= m; i ++) {
		cin >> a[i];
	}
	ans.init(1, 15), base.init(15, 15);
	ans.c[1][1] = 1;
	for(int i = 1; i <= 15; i ++) {
		base.c[i][i] = 1;
	}
	for(int i = 1; i <= 2027; i ++) {
		Matrix &t = cur[i];
		t.init(15, 15);
		for(int j = 1; j <= 14; j ++) {
			t.c[j][j + 1] = 1;
		}
		for(int j = 1; j <= m; j ++) {
			t.c[a[j]][1] = (i - a[j] + 1 + mod) % mod;
		}
		base = base * t;
	}
	ans = ans * power(base, n / 2027);
	for(int i = 1; i <= n % 2027; i ++) {
		ans = ans * cur[i];
	}
	cout <<	ans.c[1][1] << '\n';
    return 0;
}

D

tag : 二分

待补。

23NOIP10连测

8.27 day1

100+100+15=215

A

tag : 我也不知道。

乱猜就过了。

code 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1e6 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n;
string s;
LL a[N], sum[N], need[N];
// 狠狠的猜结论过大样例
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    cin >> s;
    for(int i = 0; i < n; i ++) {
    	if(s[i] == '(') a[i + 1] = 1;
    	else a[i + 1] = 0;
    }
    for(int i = 1; i <= n; i ++) {
    	sum[i] = sum[i - 1] + a[i];
    	need[i] = (i + 1) / 2;
    }
    LL res = 0;
    for(int i = 1; i <= n; i ++) {
    	res += max(need[i] - sum[i], 0ll);
    }
    cout << res << '\n';
    return 0;	
}

B

tag : 暴力？

暴力枚举每个操作能不能进行，判下是否合法。

code 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 25, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, m;
string s;
set<PII> ans;
int down_x, down_y, up_x, up_y, r, c;
int id(int x, int y) {
	x -= down_x - 1, y -= down_y - 1;
	return c * (x - 1) + y;
}
void check(int state) {
    map<int, int> mp;
    int now_x = 0, now_y = 0;
    mp[id(0, 0)] = 2;
    for(int i = 1; i <= n; i ++) {
        int nx = now_x, ny = now_y;
        if(s[i] == 'L') {
            nx --;
        }
        else if(s[i] == 'R') {
            nx ++;
        }
        else if(s[i] == 'D') {
            ny --;
        }
        else {
            ny ++;
        }
        if(state >> (i - 1) & 1) {
            if(mp[id(nx, ny)] == 1) {
                return;
            }
            now_x = nx, now_y = ny;
            mp[id(nx, ny)] = 2;
        }
        else {
            if(mp[id(nx, ny)] == 2) {
                return;
            }
            mp[id(nx, ny)] = 1;
        }
    }
    ans.insert({now_x, now_y});
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> s;
    s = " " + s;
    for(int i = 1; i <= n; i ++) {
    	if(s[i] == 'L') {
    		down_x --;
    	}
    	else if(s[i] == 'R') {
    		up_x ++;
    	}
    	else if(s[i] == 'D') {
    		down_y --;
    	}
    	else {
    		up_y ++;
    	}
    }
    r = up_x - down_x + 1, c = up_y - down_y + 1;
    for(int i = 0; i < 1 << n; i ++) {
        check(i);
    }
    cout << ans.size() << '\n';
    for(auto v : ans) {
        cout << v.first << ' ' << v.second << '\n';
    }
    return 0;
}

C

tag : 线性基

没学，待补。

D

tag : 计算几何，凸包，闵科夫斯基和

没学，待补。

23NOIP赛前20连测

还没开始。

标签：typedef,const,记录,int,LL,cin,long,模拟
From： https://www.cnblogs.com/Svemit/p/17674927.html

相关文章

  • 《返老还童》经典语句摘录，以及个人观后感记录
    目录电影个人赏析经典的语句摘录电影个人赏析  在我看来，这部电影给我最大的感受是爱、是孤独、是遗憾、是奇迹，是不断突破，在任何时候都敢于去做去实现。这是一部很感人的电影，让人不停的感慨，每次看都有不同的感受，仿佛是自己重新走过了一遍自己的人生。我们要不留遗憾的活着，去努......
  • 暑假模拟赛二 解题报告
    唐山一中模拟赛一解题报告\[\Large110\pts,\text{No.}1.\]打这场比赛的时候分心很多，基本上就是T1一眼了一下然后实现，然后就开始死摆。一会儿摸鱼一会儿躺着，最后的将近3个小时都在摆的过程中偶尔推一下T2。但显然T2打出了正解，但是由于一步小小的错误，加之结论出现了......
  • 记录centos stream 9 编译qt5.15.10源码
    开始装的一些依赖库没有记录gcc之类的，都是通过dnf安装的主要是make过程中出现的问题（qtwebengine）及其如何解决编译的命令如下./configure-prefix/home/kun/usr/Qt/5.15.10-opensource-confirm-licensemake-j16makeinstallconfigure阶段失败一般都是缺少，都是dnf解决的......
  • [做题记录]一些简单的SSTI题目
    一只网络安全菜鸟--(˙<>˙)/--写博客主要是想记录一下自己的学习过程，过两年毕业了也能回头看看自己都学了些啥东西。由于本人水平有限内容难免有错误、疏漏、逻辑不清、让人看不懂等各种问题，恳请大家批评指正如果我写的东西能对你有一点点帮助，那真是再好不过了......
  • nodejs + superagent 示例记录【2023-09-02】【尝试nodejs接口测试库】
    constsuperagent=require("superagent");(async()=>{ try{  constres=awaitsuperagent.get(   "https://jsonplaceholder.typicode.com/users"  );  constheaderDate=   res.headers&&res.headers.date?......
  • 超声检查术语记录，不懂就问，详细了解其中的细节
    NuchalTranslucency,NT检查也就是胎儿颈部透明层厚度。通过B超检查评估胎儿的颈后透明层厚度、以及胎儿鼻骨是否可见，从而帮助医生判断胎宝宝是否患有唐氏综合征等染色体异常，或是存在畸形的风险，有助于早期发现胎儿异常风险问题。这项检查应在孕11~13周+6天进行（胎儿头臀长45~8......
  • P8819 [CSP-S 2022] 星战 做题记录
    不可以，总司令。题目传送门思路首先，当图中每个点出度为\(1\)时，从任一点出发必定会进入环。证明：假设有一点不符合，则沿着它的出边一直走会到一个出度为\(0\)的「终点」，与每个点出度为\(1\)矛盾。想通了这点，这题就不难了。发现出度要\(O(n)\)维护，入度可以\(O(1)\)维护......
  • 20230829-面试题html+css5道题记录
    css预处理工具参考答案：CSS预处理器是一个能让你通过预处理器自己独有的语法来生成CSS的程序。css预处理器种类繁多，三种主流css预处理器是Less、Sass（Scss）及Stylus；它们各自的背景如下:Sass：2007年诞生，最早也是最成熟的CSS预处理器，拥有ruby社区的支持和compass这一最强大的css框......
  • 20230825-面试题html+css5篇简单记录
    html标签的类型（head，body，！Doctype）他们的作用是什么!DOCTYPE标签：它是指示web浏览器关于页面使用哪个HTML版本进行编写的指令.head：是所有头部元素的容器,绝大多数头部标签的内容不会显示给读者该标签下所包含的部分可加入的标签有base,link,meta,script,style和title......
  • 2023 逆天记录 - 1
    CF407Ek-d-sequence首先特判\(d=0\)的情况。否则显然一个合法的区间所有数\(\bmodd\)都相等。将这样的区间拉出来，一个个考察，显然可以将所有的数都\(\divd\)，这样就变成了公差\(=1\)的等差数列。一个区间\([l,r]\)合法，当且仅当：\([l,r]\)中的数两两不同。\(r-......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99