首页 > 其他分享 >表扬学长

表扬学长

时间：2024-08-11 17:49:41浏览次数：6  
标签：cnt int ll long times amx 表扬 学长

「模拟赛」暑期集训CSP提高模拟17（8.10）

虽然赛时打的并不好，但喜欢这次学长出的题。

总结写前面：

  • 签到题就是拉开排名的，签到题一般不难，就看想没想到那一步了，确定哪个是签到题之后留出时间来打正解；

  • 每道题想了过长时间没有正解思路赶紧打上暴力跳，留时间给签到题，签到题打出来了再去考虑别的题的优化或正解；

  • 注意二维背包的写法

  • T4 思路多复习，DP 由于维数过大（但答案很小），于是拿出一维和答案互换，即答案作一维，DP 数组维护原来的一维。

A.符号化方法初探 55pts

原题：ABC 081D

因为这个题被拉开分了，构造题，开始先想了 40min，没想到正解，先跳了。后来回来时间不多了，又想了 10min，太着急（当时才打了 T2 、T4 暴力），没再想，直接打了 \(55pts\) 暴力溜了。

部分分：

  • \(5pts\)：样例 1；
  • \(25pts\)： 所有数为正数时，维护一个最大值，从 1 到 \(n\) 遍历让所有小于前一个数的数都加上最大值，并更新最大值；
  • \(25pts\)： \(|a_i| \le 1\) 时，没有 1 则全置为 0，有 1 则全置为 1。

正解：

第二个部分分引导正解。显然，当序列的数全为非负数或全为非正数时每个数最多需要 1 次操作就能满足条件，所以考虑把所有数变为同号。

维护一个最大值 \(max\) 和最小值 \(min\)（记住每次操作之后要更新）：

  • 当 \(max > -min\) 时，把所有负数都加上 \(max\) 可以使所有数都为非负数；之后按照第二个部分分操作即可；
  • 否则，把所有正数加上 \(min\) （肯定为负数）可以使所有书都为非正数，之后从 \(n\) 到 1 让所有大于后一个数的数都加上最小值即可。

code：

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

const int N = 2e5 + 10;

int n, axid, inid, l[N], r[N];
ll a[N], amx, imn = 2e9;

void output(int e){
    cout<<e<<"\n";
    for(int i=1; i<=e; i++){
        cout<<l[i]<<" "<<r[i]<<"\n";
    }
}

int main(){
    // freopen("in.in", "r", stdin); freopen("out.out", "w", stdout);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        if(amx < a[i]){
            amx = a[i], axid = i;
        }
        if(imn > a[i]){
            imn = a[i], inid = i;
        }
    }

    int cnt = 0;
    if(amx > -imn){
        for(int i=1; i<=n; i++){
            if(a[i] >= 0) continue;
            a[i] += amx, l[++cnt] = axid, r[cnt] = i;
        }

        for(int i=1; i<=n; i++){
            if(a[i] >= a[i-1]) continue;
            a[i] += amx, l[++cnt] = axid, r[cnt] = i;
            if(amx < a[i]) amx = a[i], axid = i;
        }

        output(cnt);
    }
    else{
        for(int i=1; i<=n; i++){
            if(a[i] <= 0) continue;
            a[i] += imn;
            l[++cnt] = inid, r[cnt] = i;
        }

        a[n+1] = 2e9;
        for(int i=n; i>=1; i--){
            if(a[i] <= a[i+1]) continue;
            a[i] += imn, l[++cnt] = inid, r[cnt] = i;
            if(imn > a[i]) imn = a[i], inid = i;
        }

        output(cnt);
    }

    return 0;
}

B.无标号 Sequence 构造 50pts

矩阵我刚学一周，对于矩阵的一些性质什么的不是很熟练，导致这个没那么难想的题没想出来，不过情有可原，至少暴力分没挂，不像不争气的 T4（好吧其实是我太菜了）。

部分分：

  • \(50pts\) 矩阵乘法 \(n^3\) 暴力。

正解：

我们知道对于矩阵 \(A、B、C、ra\)，若 \(A\times B=C\)，那么 \(ra\times A\times B=ra\times C\)；且 \(1\times n\) 的矩阵与 \(n\times n\) 的矩阵相乘得到 \(1\times n\) 的矩阵。

所以我们构造一个 \(1\times n\) 的矩阵 \(ra\)，这样矩阵乘法的时间复杂度就变成了 \(O(1\times n^2)\)，可做了。

code：

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

const int N = 3005;
const int mod = 998244353;

int T, n, a[N][N], b[N][N], c[N][N];ll ra[N], temp[N];
ll ans1[N], ans2[N];

unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 rand_num(seed);
uniform_int_distribution<long long> dist(1, 998244353);

int main(){
	// freopen("in.in", "r", stdin); freopen("out.out", "w", stdout);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin>>T;

    while(T--)
    {
    	cin>>n;
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				cin>>a[i][j];

		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				cin>>b[i][j];

		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				cin>>c[i][j];

		bool f = 1;

		for(int i=1; i<=n; i++) ra[i] = dist(rand_num);

		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				temp[i] = (temp[i] + ra[j] * a[j][i] % mod) % mod;

		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				ans1[i] = (ans1[i] + temp[j] * b[j][i] % mod) % mod;

		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				ans2[i] = (ans2[i] + ra[j] * c[j][i] % mod) % mod;

		for(int i=1; i<=n; i++){
			if(ans1[i] != ans2[i]){f = false; break;}
		}

		for(int i=1; i<=n; i++) temp[i] = ans1[i] = ans2[i] = 0;
		

		cout<< ( f ? "Yes\n" : "No\n" ) ;

    }
	

	return 0;
}

C.无标号 Multiset 构造 5 pts

还未改。

D.有限制的构造 20 pts

原题：ABC 364E

赛时打的 \(5+15+20=40 pts\) 暴力，结果二维背包还打锅了，导致得分 \(5+15+0=20pts\)。

部分分：

  • \(5 pts\)：样例 1；

  • \(15pts\)：对于 \(n=8\) 的数据， 爆搜即可；

  • \(20pts\)：对于 \(v\le 100\) 的数据，二维背包 DP。

暴力代码（40pts） 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = 85;

int n, A, B, a[N], b[N];

namespace case3
{	
	int f[85][605][605];
	int main(){
		
		for(int i=1; i<=n; i++)	{
			for(int j=0; j<=A; j++){
				for(int k=0; k<=B; k++){
					f[i][j][k] = f[i-1][j][k];
				}
			}
			for(int j=a[i]; j<=A; j++){
				for(int k=b[i]; k<=B; k++){
					f[i][j][k] = max({f[i][j][k], f[i-1][j-a[i]][k-b[i]]+1, f[i-1][j][k]});
				}
			}
		}
		cout<<( (f[n][A][B]==n) ? n : (f[n][A][B]+1) );

		return 0;
	}
	
}

bool vis[N];
int dfs(int x, int cnt, int Aa, int Bb){
	if(Aa > A or Bb > B) return cnt;
	if(cnt == n) return n;

	int ans = 0;
	for(int i=1; i<=n; i++){
		if(vis[i]) continue;
		vis[i] = true;
		ans = max(ans, dfs(i, cnt+1, Aa+a[i], Bb+b[i]));
		vis[i] = false;
	}
	return ans;
}

int main(){
	// freopen("in.in", "r", stdin); freopen("out.out", "w", stdout);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin>>n>>A>>B; int v = max(A, B);
    for(int i=1; i<=n; i++){
    	cin>>a[i]>>b[i];
    	v = max({v, a[i], b[i]});
    }

    if(n < 12){
    	cout<<dfs(0, 0, 0, 0);
    	return 0;
    }	
	if(v <= 600){
		return case3::main();
	}

	return 0;
}

注意二维背包 DP 写法：

因为二维背包的两个条件会存在一个满足另一个不满足的情况，所以看代码。

for(int i=1; i<=n; i++)	{
	for(int j=0; j<=A; j++){ //注意这一层 j 和 k 的循环范围
		for(int k=0; k<=B; k++){
			f[i][j][k] = f[i-1][j][k];
		}
	}
	for(int j=a[i]; j<=A; j++){
		for(int k=b[i]; k<=B; k++){
			f[i][j][k] = max({f[i][j][k], f[i-1][j-a[i]][k-b[i]]+1, f[i-1][j][k]});
		}
	}
}

正解：

由于答案较小（最多只有 80）而 DP 数组开得过大，考虑把我们二维背包 DP 数组中一维与答案互换位置。

设 \(f_{i,j,k}\) 表示在前 \(i\) 个游戏里选 \(j\) 个，画面质量之和为 \(k\) 时最小的不可玩度之和，接下来怎么做显然了。

DP 状态转移部分的代码：

memset(f, 0x3f, sizeof f);
int ans = 0;
for(int i=0; i<=n; i++) f[i][0][0] = 0;
for(int i=1; i<=n; i++){
    for(int j=1; j<=i; j++){
        for(int k=A; k>=0; k--){
            f[i][j][k] = f[i-1][j][k];
            // if(f[i][j][k] <= B) ans = max(ans, j);
        }
        

        for(int k=A; k>=a[i]; k--){
            f[i][j][k] = min(f[i-1][j][k], f[i-1][j-1][k-a[i]]+b[i]);
            if(f[i][j][k] <= B) ans = max(ans, j);
        }

    }
}

code：

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

const int N = 85;

int n, A, B, a[N], b[N];
int f[81][81][10001];

int main(){
	// freopen("in.in", "r", stdin); freopen("out.out", "w", stdout);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin>>n>>A>>B; 
    for(int i=1; i<=n; i++){
    	cin>>a[i]>>b[i];
    }

    memset(f, 0x3f, sizeof f);
    int ans = 0;
    for(int i=0; i<=n; i++) f[i][0][0] = 0;
    for(int i=1; i<=n; i++){
    	for(int j=1; j<=i; j++){
			for(int k=A; k>=0; k--){
				f[i][j][k] = f[i-1][j][k];
				// if(f[i][j][k] <= B) ans = max(ans, j);
			}
    		

    		for(int k=A; k>=a[i]; k--){
    			f[i][j][k] = min(f[i-1][j][k], f[i-1][j-1][k-a[i]]+b[i]);
    			if(f[i][j][k] <= B) ans = max(ans, j);
    		}

    	}
    }

    cout<<((ans == n) ? n : ans + 1);


	return 0;
}

标签：cnt,int,ll,long,times,amx,表扬,学长
From： https://www.cnblogs.com/YuenYouth/p/18353048

相关文章

  • 评价一下学长组的比赛
    1.怀特布莱克专场2.gtm学长专场3.满穗专场rnk1奖励跟原图还有点像4.节目效果专场5.交互题和提交答案题专场6.数学专场7.二次元(Saber)专场持续断更......
  • OI 回忆录 2 - 我的学长们
    cxr说起学长，这就不得不先提到cxr了。他自己本身就非常强，高一进入集训队，创造qzez历史，于是在高二的时候非常照顾初三的我们日常训练，包括帮助调题、提供模拟赛等等方方面面。每次来到机房的时候cxr总是坐在固定的那个位置，cxr就是我们的老大哥，我们的主心骨。cxr在机房的时......
  • joke 学长出题比赛记录
    早上吃饭呢路上Qyun:gtm学长旁边那个穿黑衣服的好像joke学长啊。几分钟后坐电梯：哇哦，还真是，joke学长来了。（我们为什么能认出来joke呢，见本篇博客最下方）7:30开赛，看见题目列表：，爆炸！随后整个机房充满了各种声音。显然，出题人的目的达到了。哇，joke学长以为要坐牢了，想着没事......
  • 派森学长带你学python—字符串
    一.字符串（1）字符串数据类型和整型、浮点型都是python中的不可变数据类型接下来我们将学习：字符串的三种界定符号、转义字符和原字符。'''字符串、整型、浮点型都是不可变数据'''name='marry'address="北京朝阳"favor='''游泳，篮球，羽毛球，赛车'''print(name)print(add......
  • 为师妹写的《Java并发编程之线程池十八问》被表扬啦！
    写在开头  之前给一个大四正在找工作的学妹发了自己总结的关于Java并发中线程池的面试题集，总共18题，将之取名为《Java并发编程之线程池十八问》，今天聊天时受了学妹的夸赞，心里很开心，毕竟自己整理的东西对别人起到了一点帮助，记录一下！Java并发编程之线程池十八问  经......
  • 给师妹写的《Java并发编程之线程池十八问》被表扬啦！
    写在开头  之前给一个大四正在找工作的学妹发了自己总结的关于Java并发中线程池的面试题集，总共18题，将之取名为《Java并发编程之线程池十八问》，今天聊天时受了学妹的夸赞，心里很开心，毕竟自己整理的东西对别人起到了一点帮助，记录一下！Java并发编程之线程池十八问  经过之前......
  • 2024学长毕设开发文档
    Django后端1、跨域请求处理问题描述直接在前端axios请求中访问后端端口：会出现跨域问题跨域的知识：处理方案：（基于django-cors-headers处理跨域）成功请求结果：2、前端访问后端资源文件setting.py设置资源文件存储路径MEDIA_ROOT配置请求资源路径......
  • 今天帮学长写页面了QVQ
    functionecharts_3(){varmyChart=echarts.init(document.getElementById('echart3'));varyears=['2008','2009','2010','2011','2012','2013','2......
  • 4.15学长自选题
    D题题意：把给定的一个数字数列放到对角线上，其他位置填写min（横，竖）。要求找到一个矩形，分别把所有的1，2，3....k都包含起来输出其长+宽思路：找到最远的那个即可，然后(mx-mn+1)*2#include<bits/stdc++.h>usingnamespacestd;#definefifirst#definesesecond#defineIO......
  • 经过腾讯云这波故障，我想表扬的点和学到的职场保命法则。
    你好呀，我是歪歪。昨天分享了一下《腾讯云4月8日故障复盘及情况说明》，较为详细的描述了故障前后的具体情况。按照惯例，这种大公司的故障说明，歪师傅都是要好好看一下的。一来是看看有没有可以学习的地方，多从别人的事故中总结经验教训，学习避坑指南。二来还可以蹭个热点。表扬......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99