首页 > 其他分享 >DAY3-补题

DAY3-补题

时间:2024-10-03 18:33:10浏览次数:10  
标签:int 合并 DAY3 long while MAXN 补题 dp

一题之计在于补呐

补题很快乐的一点就是看不懂且听不明白但是写注释中理解到了。

果然学会一道题最简单的方式是给一个纯萌新讲。

说在前面

今天%你赛手感非常好,可能是换了一个位置的原因(玄

首先T1没有读错题是一个比较大的进步,因为DAY1和2都是因为差不多这个原因寄掉了,读对题目果然可以A掉还不错。T2做题的时候没有想到正解就很逆天,赛后重构发现第一遍敲代码时有一部分思想重合了但没发现可以这么做(因为zj是直接找到 pos 的位置,但我的代码是按照正解又模拟的(屑

T3赛时一眼合并果子弱化版的强化版(指不需要桶排但一次可以合并 m 个。赛后发现要考虑直接合合不了的情况。T4搓了一个部分分就跑路了,赛后又发现加个判断可以多拿三十(今天还是很屑。

很屑的是有一道题直接输出YES有70pts,总司令又又又可以了。

所以挂掉(指可以拿到的但没有拿到)居然达到了惊人的90分。数据加强谢谢。

最后得分:100+20+10+10 = 140,个人觉得属于不怎么好但比前几天好的情况了。

但今天没有彩蛋也没有1145141919810就很不好

T1-IP地址(ip)

赛时敲出正解。

模拟即可。当时 map 忘掉怎么写了,所以手搓结构体,本来觉得会爆掉时间复杂度,但一看范围 \(10^5\) 快乐A。

笑点解析:老师说要 scanf,写了之后好像有同学挂掉了。

锐评:不如手敲读优。

歪解:

#include <iostream>
#include <map>
using namespace std;
struct Node {
	string s,s1;
}a[1005];
void read(long long &x){ 
	int f = 1;
	x = 0;
	char s = getchar();
	while(s < '0' || s > '9') {
		if(s == '-') f = -1;
		s = getchar();
	}
	while(s >= '0' && s <= '9') {
		x = x * 10 + s - '0';
		s=getchar();
	}
	x *= f;
}
int main() {
//	freopen("ip.in","r",stdin);
//	freopen("ip.out","w",stdout);
	cin.tie();
	cout.tie();
	long long n;
	read(n);
	for(int i = 1; i <= n; i ++) {
		cin >> a[i].s >> a[i].s1;
	} 
	int q;
	cin >> q;
	for(int i = 1; i <= q; i ++) {
		string s2;
		cin >> s2;
		for(int j = 1; j <= n; j ++) {
			if(a[j].s1 == s2) cout << a[j].s << endl;
		}
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
} 

正解改成 map 即可。

T2 - 是否同构(same)

赛时敲到20。

TLE只能说明我的算法不够优啊,枚举k本来就是一个不怎么高明的方法,只能说当时指向正解的指针可能歪掉了。

放一下代码:

#include <iostream>
#define int long long 
using namespace std;
const int MAXN = 1e6 + 10;
int a[MAXN], b[MAXN];
void read(long long &x){ 
	int f = 1;
	x = 0;
	char s = getchar();
	while(s < '0' || s > '9') {
		if(s == '-') f = -1;
		s = getchar();
	}
	while(s >= '0' && s <= '9') {
		x = x * 10 + s - '0';
		s=getchar();
	}
	x *= f;
}
signed main() {
//	freopen("same.in","r",stdin);
//	freopen("same.out","w",stdout);
	int t;
	cin >> t;
	while(t --) {
		int n;
		cin >> n;
		for(int i = 1; i <= n; i ++) cin >> a[i];
		for(int i = 1; i <= n; i ++) cin >> b[i];
		int flag2 = 0;
		for(int i = 1; i <= n / 2; i ++) { // 枚举k 
		    int flag = 0;
			for(int j = 1; j <= n - i; j ++) {
				swap(a[j], a[n - i + 1]);
			} 
			for(int i = 1; i <= n; i ++) {
				if(a[i] != b[i]) {
					flag = 1;
					break;
				}
			}
			if(flag == 0) {
				cout << "No\n";
				flag2 = 1;
				break;
			}
		}
		if(flag2 == 0) cout << "Yes\n";
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}
//3
//3
//1 2 3
//3 2 1
//4
//3 1 2 4
//4 3 1 2
//5
//2 3 1 4 5
//5 3 1 4 2

正解是很好想的办法,在 \(a\) 数组里找 \(b_{1}\) 出现的位置,然后记录下来,也就是 pos

接着安照题意 swap 即可。

正解:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int a[MAXN], b[MAXN], n;
bool check() {
    for(int i = 1; i <= n; i ++) if(a[i] != b[i]) return 0;
    return 1;
}
int main() {
    int t;
    cin >> t;
    while(t --) {
        cin >> n;
        for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
        for(int i = 1; i <= n; i ++) scanf("%d", &b[i]);
        int flag = 0;
        if(check()) {
            printf("Yes\n");
            flag = 1;
            continue;
        }
        int pos = 0;
        for(int i = n - (n / 2) + 1; i <= n; i ++) {
            if(a[i] == b[1]) {
                pos = i;
                break;
            }
        }
        for(int i = pos; i <= n; i ++) {
            swap(a[i], a[i - pos + 1]);
        }
        if(check()) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

T3-箱子(box)

赛时敲掉样例。

但样例过水以至于没有发现需要补0,补上0之后分数果真补0了。

优先队列自动排序不用管,每次选最小(也就是贪心就好),因为第一次选的肯定是最多次的,所以越小越好,这就是这道题的思路。

很好的是贪心是可以的,我们可以试图证明一下。

贪心思路:每次选最小的装进去。

下面思路来自于this

证明不断取最小的两堆合并成较大的一堆是最优的。

最优方案可以表示成一个二叉树。
\(总代价 \sum_{i=1}^{n} a_i × depth_i∑ i=1 \)其中 \(depth\) 是深度,也就是这堆果子在整个过程中被有效合并了几次。

注意:\(a_i\) 都是叶子结点。非叶子结点都是合并后的产物。

②最小的两堆一定在最优方案树的最深层。

这个用反证法。假设有一个最优方案树,其最深层中没有最小的两堆。那么把最小的堆与最深层的某堆互换位置形成新方案,保证新方案存在而且新方案的代价小于原方案。

注意:最深层总是一组(一组有两个)或多组叶子节点,来表示它们被直接合并。

③同层叶子节点互换,对总代价无影响。

根据①的 \(\sum\) 得。可见,最小的两堆,如果在最优方案树最深层中不是即将合并的一组,那么可以无偿换为一组。

④根据上两步,我们已经明确:最优方案需要直接合并当前最小的两堆。现在我们就进行这个操作。事实是:现在只剩 \(n-1\) 堆了。

我们只知道刚才进行了一个绝对不错的操作,而不记得操作之前是什么样的。我们只想对现在剩下的几堆陌生的果子进行最好的操作。忽略之前的树,于是回到①了。

注意:这并不意味着之前一步的操作使日后的代价和非常优秀。

显然的,延伸到取 \(m\) 个也是同样的思路。

大佬思路真的很清晰啊啊啊。(土拨鼠嚎叫

所以说是 https://www.luogu.com.cn/problem/P1090 的加强版也没有什么问题对不对。

正解思路:

观察到每次把 \(m\) 个合并成 \(1\) 个相当于减去了 \(m - 1\) 个,然后我们可以分两种情况讨论:

  • \((n-1)\space mod\space (m - 1) = 0\) 这种情况我们每次取 个合并最终可以刚好合并成一个,然后我们使用一个小根堆,每次取最小的 \(m\) 个合并即可。

  • \((n-1)\space mod\space (m - 1) ≠ 0\) 这种情况一定会发生一次当前剩余数量不够 \(m\) 个的情况,那么我们可以补足若干个 \(0\),使得满足\((n-1)\space mod\space (m - 1) = 0\),然后我们按照上述方法做即可,此方法等价于在第一次合并的时候少选几个箱子,以便让后面的合并可以每次都取 \(m\) 个。

扔下正解:

#include <bits/stdc++.h>
using namespace std;
long long n,m,x,ans;
priority_queue<long long,vector<long long>,greater<long long> >q;
void read(long long &x){ 
	int f = 1;
	x = 0;
	char s = getchar();
	while(s < '0' || s > '9') {
		if(s == '-') f = -1;
		s = getchar();
	}
	while(s >= '0' && s <= '9') {
		x = x * 10 + s - '0';
		s=getchar();
	}
	x *= f;
}
int main(){
//	freopen("box.in","r",stdin);
//	freopen("box.out","w",stdout);
	read(n);
	read(m);
	for(int i = 1; i <= n; i ++) {
		read(x);
		q.push(x);
	}
	if((n - 1) % (m - 1) > 0) {
		int cnt = m - 1 - (n - 1) % (m - 1);
		while(cnt --) q.push(0);
	}
	while(!q.size()){
		long long cnt = 0;
		bool f = 0;
		for(int i = 1; i <= m; i ++) {
			if(!q.size()) {
			cnt += q.top();
		//	cout << q.top() << " ";
 			q.pop();
			} else {
				f = 1;
				break;
			}
		}
		if(f) break;
		q.push(cnt); 
		ans += cnt;
	}
	printf("%lld",ans);
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

T4-社恐的聚会(party)

行了这道题不会就算了吧。

挣扎一下,眼前一亮,出题人非常良心的给了什么?!是部分分啊,可是不用动脑子就能拿到的10分啊!

其实再动一下脑子,发现加上一个判断可以多拿30pts。

最后我们来分析一下正解(因为作者真的蒟蒻不会正解)

我们把所有不互相认识的人之间连一条无向边,然后我们可以对于所有连通块判断当前连通块是否是二分图(使用黑白染色法)。

要素过多了哈。

  • 不互相认识的人:指的是我们建图之后两个人中间不是双向的,也就是A认识B但B不认识A,当然也就是我们正解代码中的:if(!g[i][j] || !g[j][i]),同样的,他等效于 !(g[i][j]&&g[j][i])

如果不是二分图,则直接输出 NO ,否则我们可以记录一下每个连通块中黑点的数量和白点的数量(代表在第一张桌子还是第二张桌子)。注意,黑点和白点本质没有任何区别,我们每个连通块都可以黑白互换。然后我们求得每个连通块的黑点和白点数量后,我们可以做一遍判定性背包dp来求解答案。

  • 如果不是二分图,则直接输出 NO:显然的偏分技巧。

  • 我们每个连通块都可以黑白互换:本质上只是一个标记的方法,用什么颜色都可以的喵。

  • 我们可以做一遍判定性背包dp来求解答案:这也是这道题最好的地方,因为我看不懂dp本质上是有决策的递归(似乎不是来着,反正不是搜索就是dp)。明显的,这道题爆搜会炸掉

具体的,设 \(dp_{i,j,0}\) 表示前 \(i\) 个连通块,是否能塞入 \(j\) 个点到第一张桌子(白点)。设 \(dp_{i,j,1}\) 表示前 \(i\) 个连通块,是否能塞入 \(j\) 个点到第二张桌子(黑点)。

  • 注意每个连通块的黑点和白点是可以互换的。

这个解释非常详细的说明了思路,同时也没有想过我们这种xxs听不懂的问题,不过没关系,代码里的注释比较详细。

dp在老师讲完之后倒是比较清晰了。昨天时候讲的图今天完全不会用,果真是蒟蒻了。

本题知识点:二分图,链式前向星,存在性dp,dfs……

总之是一道超纲的题目。放到明天骗分专场倒是不错。

正解:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 525;
int head[MAXN], nxt[MAXN * MAXN], to[MAXN * MAXN],cnt;
void add(int u, int v) {
    nxt[++ cnt] = head[u];
    to[cnt] = v;
    head[u] = cnt;
} // 构造一个链式前向星存一下
// 整篇代码唯一简单易懂的地方(真的简单易懂哈
int n, g[MAXN][MAXN];
bool vis[MAXN];
int color[MAXN], sz[MAXN][2], idx; // 翻译一下,size是长度的喵
// idx是目标,Coler是可爱的颜色
// 这就关系到这道题第二个地方——黑白染色(
// 因为看不懂所以可爱到了
bool dfs(int u, int c) { // 是一个dfs,看函数名字就能看出来
    // 主要作用是判断是否为二分图
    // 因为只有两张桌子对不对?所以二分图(胡说
    vis[u] = true;
    color[u] = c;
    sz[idx][c] ++;
    for(int i = head[u]; i ; i = nxt[i]) {
        int v = to[i];
        if(vis[v]) {
            if(color[u] == color[v]) return 0; // 判断为假
            else {
                if(!dfs(v, c ^ 1/*相当于取反,因为c不是1就是0*/)) return 0;
            }
        }
    }
    return 1;
}
bool dp[MAXN][MAXN][2]; // 是的你没有看错,这里还有一个dp
// 而且是非常高级的存在性dp,简称不会的dp
int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= n; j ++) {
            cin >> g[i][j];
        }
    }
    for(int i = 1; i < n; i ++) {
        for(int j = i + 1; j <= n; j ++) {
            if(!g[i][j] || !g[j][i]) {
                //=>!(g[i][j]&&g[j][i])
                //=>只有相互认识的时候才不会产生连边,其他的情况都加边放图中
                add(i,j);
                add(j,i);
            }
        }
    }
    for(int i = 1; i <= n; i ++) {
        if(vis[i]) continue;
        idx ++;
        if(!dfs(i,0)) {
            cout << "No\n";
            return 0; // 这是这段代码最友善的地方,给了部分分且不是多测很好
        }
    }
    dp[0][0][0] = true;
    dp[0][0][1] = true;
    int mx = n / 2;
    for(int i = 1; i <= idx; i ++) {
        for(int j = sz[i][0]; j <= mx; j ++){
            dp[i][j][0] |= dp[i - 1][j - sz[i][0]][0];
            dp[i][j][0] |= dp[i - 1][j - sz[i][0]][1]; 
            // 一个小dp,判断分在哪个桌子
        }
        for(int j = sz[i][1]; j <= mx; j ++){
            dp[i][j][1] |= dp[i - 1][j - sz[i][1]][0];
            dp[i][j][1] |= dp[i - 1][j - sz[i][1]][1];
        }
    }
    int ans = 0;
    for(int j = mx; j >= 1; j --){
        if(dp[idx][j][0] || dp[idx][j][1]){
            ans = n - j;
            break;
        }
    }
    cout << "Yes" << endl;
    cout << ans << endl;
    return 0;
}

点赞关注喵,点赞关注谢谢喵。

标签:int,合并,DAY3,long,while,MAXN,补题,dp
From: https://www.cnblogs.com/Cherry929/p/18445878

相关文章

  • 补题报告3
    背景2024-10-3上午打的比赛(CSP-J模拟2),作赛后总结报告。IP地址(\(ip\))赛时AC。概述每个设备有一个对应的\(IP\),先给出对应的设备与\(IP\),再给出几个\(IP\),求对应的设备。思路\(map\)存储,映射我的代码代码(点左边三角展开)#include<map>#include<cstdio>#includ......
  • CSP-J模拟赛补题报告
    前言最SB的一次&做的最差的一次T1:AC100pts......
  • 补题报告2
    背景2024-10-2上午打的比赛(CSP-J模拟2),作赛后总结报告。下棋(\(chess\))赛时AC。概述高星\(x\)中星\(y\)低星\(z\)\(3\timesz=y\)\(3\timesy=x\)阵容强度:\(18\timesx+3\timesy+z\)求转换完后强度的顺序思路1.将能转的低星英雄转高星2.结构体排序输出......
  • DAY2-补题
    我补题AK了,但你出言不逊是非常好的一套题,让我的大脑旋转啊。不太想开一个文章单独屑,所以扔到随笔里面。敲字速度有待加强。说在前面题目难度单调递减,分数单调递减。果然屑死了。T1再次读题失误,正确的来说是代码敲得非常抽象。T2DP但没骗到分非常不好,T3场上想出正解了,但推一......
  • 补题报告
    背景2024-10-1上午打的比赛(CSP-J模拟),作赛后总结报告。交替出场(Alter)赛时AC。思路1.先将结果数设为长度(默认每个长度为1的子串符合要求)2.遍历每个子串,判断是否满足01交替串,是+13.输出我的代码#include<iostream>#include<string>#include<cstring>#i......
  • DAY1-补题
    说句闲话:研究补题最好的方式是补完AK了,祝你们成功(滑稽此文章仅作为补题,题解等我理解完掉重新写。比赛情况不可饶恕的错误(滑稽赛时第一题看错题意,导致明明可以做掉的内容爆了,T2考虑到了正解,可一直在推式子和打表中间晃荡,遗憾。T3很好笑,没有删除调试语句,赛后删了重交过到了30pt......
  • leetcode刷题day34|动态规划Part03 背包问题(01背包问题 二维、01背包问题 一维、416.
    0-1背包问题二维动规五部曲1、确定dp数组以及下标的含义dp[i][j]表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。(取物品时可以是取0-i的任意一个,或者是他们的组合)2、确定递推公式不放物品i:背包容量为j,里面不放物品i的最大价值是dp[i-1][j]......
  • leetcode刷题day33|动态规划Part02(62.不同路径、63. 不同路径 II、 343.整数拆分、96.
    62.不同路径机器人从(0,0)位置出发,到(m-1,n-1)终点。动规五部曲1、确定dp数组(dptable)以及下标的含义dp[i][j]:表示从(0,0)出发,到(i,j)有dp[i][j]条不同的路径。2、确定递推公式想要求dp[i][j],只能有两个方向来推导出来,即dp[i-1][j]和dp[i][j-1]。dp[i]......
  • CSP-S 2022~2023 补题
    下面的代码都是远古代码,不打算重写了。CSP-S2023T1密码锁题意:一个密码锁上有\(5\)个位置,每个位置上的数字是\(0\sim9\)的循环,每次打乱会选择一或两个相邻位置同时循环移动。给定\(n\)个打乱后的状态,求有多少种可能的原状态。\(n\le8\)。容易发现可能的状态数......
  • NOIP2024集训Day37 DP
    NOIP2024集训Day37DPA.[CQOI2011]放棋子设\(f_{i,j,k}\)表示前\(k\)种棋子放了任意\(i\)行、\(j\)列。决策是:在哪些位置填同种颜色的棋子。于是美剧上一个状态的\(i,j\)(表示为\(l,r\)),上一状态\(k_1=k-1\)。设\(g_{i,j,k}\)表示\(k\)个同种颜色的......