首页 > 其他分享 >8.8 个人赛

8.8 个人赛

时间：2023-08-09 20:56:03浏览次数：51  
标签：la int 8.8 long maxn tie 个人赛 define

比赛链接: https://www.luogu.com.cn/contest/124225#description


A - 三值的排序

难度 ⭐⭐

解题思路

如果a在b应在的位置上, 同时还有个b在a应在的位置, 这时候交换a和b是最优的, 因为交换后就不需要再调整了; 因此我们先把序列排序, 找到每个数应该在哪个区间内; 然后遍历原序列并和排好序的序列作比较, 如果原序列该位置为a, 而排好序的序列该位置为b, 就用map把{a,b}出现的次数记录下来, 说明有多少个a处在了b应在位置上; 这样找出所有矛盾后, 遍历所有可能的情况, 对于mp[{i, j}]和mp[{j, i}], 让它们减去它们当中较小的那个, 而这个较小的数就是最优情况交换的次数; 找完所有最优情况后, 我们只需要遍历1和2的所有情况, 并且将其归为即可, 因为1和2都归为后3自然也归为了, 如果把3的情况也算上反而重复了;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10, mod = 1e9 + 7;
int n, m, res;
int x1, x2;
int f[N], g[N];
map<PII, int> mp;
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> f[i];
        g[i] = f[i];
    }
    sort(g + 1, g + 1 + n);
    for (int i = 1; i <= n; i++) {
        if (f[i] != g[i]) {
            mp[{ f[i], g[i] }]++;
        }
    }
    for (int i = 1; i <= 3; i++) {
        for (int j = i+1; j <= 3; j++) {
            int a = min(mp[{i, j}], mp[{j, i}]);
            mp[{i, j}] -= a;
            mp[{j, i}] -= a;
            res += a;
        }
    }
    for (int i = 1; i <= 2; i++) {
        for (int j = 1; j <= 3; j++) {
            if (i == j) continue;
            if (mp[{i, j}]) res += mp[{i, j}];
        }
    }
    cout << res;
    return 0;
}



B - 天际线

难度 ⭐⭐⭐⭐

解题思路

一道熟悉的题目, 来还债了属于是...这次正经地用线段树做一下; 因为本题是区间修改, 所以除了一般的左右节点和最大值外我们还需要维护一个懒标记la, 表示这个区间在最高la这个高度是平坦的, 所以如果一个区间最终是平坦的, 那么这个区间的la和maxn相等; 建好树后开始修改操作, 如果该范围包含当前区间, 那么更新最大值和懒标记: maxn=max(maxn, h), la=max(la,h); 如果不完全包含就还是pushdown+左右区间+pushup三件套, pushup就用来更新父节点的最大值, 而pushdown需要用父节点的la去更新左右节点, 注意是用la而不是maxn, maxn只是父节点区间的最大值, 而la是整个父节点区间都可以达到的一个高度, la是可以去影响子节点的; 所以对于左右节点: maxn=max(maxn, fla), la=max(la,fla);
因为坐标最大为1e4, 我们可以去查询每个坐标的最大值, 然后把变化的地方输出即可; 查询时query(1, i, i), 所以当l=i&&r=i时输出这个区间的maxn即可(其实是一个点); 否则就pushdown之后从左右区间找即可;
本题的关键还是在于对la的理解, maxn只是用来最后找答案, 在修改过程中操作的重点的还是la; 而且, 因为这个题最后是找每个点的高度, 所以我们甚至可以把maxn和pushup删去, 因为根据我们对la这个懒标记的定义, 对于点这个区间, 能让其平坦的最大高度就是maxn;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4+10, mod = 1e9 + 7;
int n, m;
int h[N];
struct str {
	int l, r;
	int maxn, la;
}tr[4*N];
void pushup(int u) {
	tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
}
void pushdown(int u) {
	auto & root = tr[u], & left = tr[u << 1], & right = tr[u << 1 | 1];
	if (root.la) {
		left.maxn = max(left.maxn, root.la);
		left.la = max(left.la, root.la);
		right.maxn = max(right.maxn, root.la);
		right.la = max(right.la, root.la);
		root.la = 0;
	}
}
void build(int u, int l, int r) {
	tr[u] = { l,r };
	if (l == r) return;
	else {
		int mid = l + r >> 1;
		build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	}
}
void modify(int u, int l, int r, int a) {
	if (tr[u].l >= l && tr[u].r <= r) {
		tr[u].maxn = max(tr[u].maxn, a);
		tr[u].la = max(tr[u].la, a);
	}
	else {
		pushdown(u);
		int mid = tr[u].l + tr[u].r >> 1;
		if (l <= mid) modify(u << 1, l, r, a);
		if (r > mid) modify(u << 1 | 1, l, r, a);
		pushup(u);
	}
}
int query(int u, int l, int r) {
	if (tr[u].l == l && tr[u].r == r) {
		return tr[u].maxn;
	}
	else {
		pushdown(u);
		int mid = tr[u].l + tr[u].r >> 1;
		int res = 0;
		if (l <= mid) res=query(u << 1, l, r);
		if (r > mid) res =query(u << 1 | 1, l, r);
		return res;
	}
}
signed main() {
	IOS;
	int a, b, c;
	build(1, 1, 10000);
	while (cin >> a >> b >> c) {
		modify(1, a, c - 1, b);
	}
	for (int i = 1; i <= 10000; i++){
		h[i] = query(1, i, i);
	}
	for (int i = 1; i <= 10000; ++i){
		if (h[i] != h[i - 1]){
			printf("%d %d ", i, h[i]);
		}
	}
	return 0;
}



C - Bond

难度 ⭐⭐

解题思路

由n的范围只有20可以想到用状压dp, 状态表示: dp[i]表示用前k个人完成k个任务的最大成功率, i为当前完成哪些任务的状态, k是i中1的个数; 状态计算: dp[i] = max(dp[i], dp[i - (1 << (j-1))] * f[k][j]); f[k][j]表示第k个人完成第j个任务的成功率; 所以我们每次只考虑第k个人完成哪个任务即可, 算是比较典型的一个dp处理方式;
警钟敲烂!!!最后输出的时候记得要用printf, cout输出是默认保留小数点前后6位, 而printf才是保留小数点后6位;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 21, mod = 1e9 + 7;
int n, m;
double dp[1 << N], f[N][N];
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            double a;
            cin >> a;
            f[i][j] = a * 0.01;
        }
    }
    dp[0] = 1.0;
    for (int i = 1; i < 1 << n; i++) {
        int k = i, num = 0;
        while (k) {
            if (k & 1) num++;
            k >>= 1;
        }
        for (int j = 1; j <= n; j++) {
            if (i >> (j-1) & 1) {
                double x = dp[i - (1 << (j-1))];
                dp[i] = max(dp[i], x * f[num][j]);
            }
        }
    }
    printf("%lf", dp[(1 << n) - 1] * 100);
    return 0;
}



D - DEATHSTAR

难度 ⭐

解题思路

既然第i行是用ai和其他数做与运算, 那么对于所有b(i,j)来说, ai是1的位上它们也得是1, 反过来也一样, 所以我们可以把第i行的所有数做与操作, 那么结果一定是ai的一种可能;

神秘代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N=1e3+10;
int n, m;
int f[N][N], q[N];
signed main() {
	cin>>n;
	for(int i=1;i<=n;i++){
	    for(int j=1;j<=n;j++){
	        cin>>f[i][j];
	    }
	}
	for(int i=1;i<=n;i++){
	    for(int j=1;j<=n;j++){
	        q[i]|=f[i][j];
	    }
	}
	for(int i=1;i<=n;i++){
	    cout<<q[i]<<' ';
	}
	return 0;
}



E - 瑞瑞的木板

难度 ⭐⭐

解题思路

贪心问题, 我们可以把切割问题看作是拼接问题, 对于a=b+c, 我们可以选择合成b或者c, 因为最后的和是一样, 如果我们合成b的话, 无论c多大, 这次拼接花费的能量就是a, 所有我们可以c是较大的那个, 我去合成较小的那个数, 所以我们可以用堆去维护当前所有木条的顺序, 每次拼接时条最小的两条合并即可;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10, mod = 1e9 + 7;
int n, m, res;
int f[N];
priority_queue<int, vector<int>, greater<int>> q;
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        q.push(a);
    }
    while (q.size()>1) {
        int a = q.top();
        q.pop();
        int b = q.top();
        q.pop();
        res += a + b;
        q.push(a + b);
    }
    cout << res;
    return 0;
}



F - Load Balancing S

难度 ⭐⭐⭐

解题思路

因为是问四个二维区间的最小值, 所以我们可以用二维前缀和把区间和处理出来; 因为N的数量只有1000, 而坐标是1e6, 所以我们可以进行离散化处理, 然后枚举两条栅栏的坐标即可, 约为1e7的复杂度, 所以不会超时; 需要注意的是离散化返回的值也得是奇数, 因为有2n的坐标, 所以离散化后坐标的最大值是4n+1; 所以记得设置好边界;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 4e3+50, mod = 1e9 + 7;
int n, m;
vector<int> v;
PII g[N];
int f[N][N];
int find(int u) {
    auto t = lower_bound(v.begin(), v.end(), u) - v.begin();
    return 2 * t + 1;
}
signed main() {
    IOS;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        g[i] = { a,b };
        v.push_back(a);
        v.push_back(b);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 1; i <= n; i++) {
        int a = find(g[i].first), b = find(g[i].second);
        f[a][b]++;
    }
    n = n * 4 + 10;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
        }
    }
    int minn = 1e9;
    for (int i = 2; i <= n; i+=2) {
        for (int j = 2; j <= n; j += 2) {
            int a = f[i][j];
            int b = f[n][j] - f[i][j];
            int c = f[i][n] - f[i][j];
            int d = f[n][n] - a - b - c;
            int maxn = max(max(a, b), max(c, d));
            minn = min(minn, maxn);
        }
    }
    cout << minn;
    return 0;
}



H - 查单词

难度 ⭐⭐

解题思路

一道比较裸的线段树, 只不过把数据类型改为了字符串, 对此自己写一个max函数即可; 其他操作和线段树的模板差不多, 就不过多赘述了;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 5e4 + 10, mod = 1e9 + 7;
int n, m;
string f[N];
struct str{
    int l, r;
    string maxn;
}tr[4*N];
string cmax(string a, string b) {
    int len = min(a.size(), b.size());
    for (int i = 0; i < len; i++) {
        char c = a[i], d = b[i];
        if (c < 'a') c += 32;
        if (d < 'a') d += 32;
        if (c > d) return a;
        else if (c < d) return b;
    }
    if (a.size() < b.size()) return b;
    else return a;
}
void pushup(int u) {
    tr[u].maxn = cmax(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
}
void build(int u, int l, int r) {
    if (l == r) tr[u] = { l,r,f[l] };
    else {
        tr[u] = { l,r };
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
string check(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].maxn;
    else {
        string res;
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) res = check(u << 1, l, r);
        if (r > mid) res = cmax(res, check(u << 1 | 1, l, r));
        return res;
    }
}
signed main() {
    IOS;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> f[i];
    }
    build(1, 1, n);
    for (int j = 1; j <= m; j++) {
        int a, b;
        cin >> a >> b;
        cout << check(1, a, b) << endl;
    }
    return 0;
}



I - 还是 N 皇后

难度 ⭐⭐⭐⭐

解题思路

如果用之前的方法的话一定会超时, 本题的用意是想用位运算进行优化, 因为我们dfs是相当于枚举每一行, 所以我们可以用二进制表示当前这一行哪些位置可以放, 哪些位置不能放, 影响因素有四个: 一是输入给定的不能放的位置为1; 二是列, 如果第i位上已经有皇后了, 那么这一行第i位就是1; 三是主对角线, 如果上一行的第i位上有皇后了, 那个这一行的第i+1位就是1, 四是副对角线, 如果上一行的第i位上有皇后了, 那个这一行的第i-1位就是1; 把这四种情况进行与操作就得到了第i行的状态;
注意边界处的对角线情况可能会让二进制多出1位, 所以我们处理完后要和(1 << n) - 1进行一次与操作, 把多出来的1去掉;
这样我们就得到了第i行的状态表示, 然后我们取反, 这样状态中1的位置就是可以放皇后的位置, 可以用lowbit操作去获取1的位置;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 1e3+10, mod = 1e9 + 7;
int n, m, res, full;
int stu[N];
void dfs(int c,int ld, int rd, int u) {
	if (c == full) {
		res++;
		return;
	}
	int p = ~(c | ld | rd | stu[u]);
	p = p & full;
	while (p) {
		int a = p & -p;
		p -= a;
		dfs(c + a, (ld + a) >> 1, (rd + a) << 1, u + 1);
	}
}
signed main() {
	IOS;
	cin >> n;
	full = (1 << n) - 1;
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		int a = 0;
		for (int j = 0; j < s.size(); j++) {
			if (s[j] == '.') a |= (1 << n-j-1);
		}
		stu[i] = a;
	}
	dfs(0, 0, 0, 1);
	cout << res;
	return 0;
}

标签：la,int,8.8,long,maxn,tie,个人赛,define
From： https://www.cnblogs.com/mostimali/p/17617878.html

相关文章

  • 2023.8.89周三：输入带空格的字符串
    1.#include<string>strings;getline(cin,s);2.#include<cstring>#include<stdio.h>chara[1024];gets(a);intlen=strlen(a);//得到数组的实际长度//！！！！！！！！！！！！！！注：cin和getline不能连着用，中间需要加一个cin.ignore;......
  • 8.7 个人赛
    比赛链接:https://www.luogu.com.cn/contest/123979#descriptionA-PhoneList难度⭐解题思路一道比较裸的trie树的题;但是我在题解中发现了一个很有意思的做法,就是通过把字符串进行排序,如果存在a是b的前缀,那个a和b一定紧挨着;神秘代码//正常做法#include<bi......
  • 2023.8.8
    今天学习的stacksmash，看了一些，ctfwiki上例题的源代码有些地方看不太懂，感觉可能要结合文件来看，而我只是去看了ctfwiki上展示的代码部分，然后我往后看到了exp部分之前，感觉好像一些源代码里看不太懂的东西可以在调试的时候了解到相关的东西。但是我又觉得可能真要我做题，到时候可能想......
  • 8.8
    周二：实在是对我的长头发厌倦了上午去理发店剪短了但是我的头发又软又塌还得再烫一下搞了摩根烫总感觉这烫头不烫不行烫了也不咋地恶心死了这头发今天学了方法的综合练习感觉有一点难了......
  • 2023.8.8 模拟赛
    A试构造不多于\(n\)个的数，满足每个数都是\(n!\)的约数，且和为\(m\).\(T\le10^5\)组数据。我们这样构造：直到\(m=0\).设一个数\(s=1\)，枚举\(i=n\sim1\)，若\(s\cdoti<m\)，使得\(s\leftarrows\cdoti\).令\(m\leftarrowm-s\).并把\(s\)加入数组中。B有\(n\)......
  • PYYZ 8.8
    8.8比赛80%瓜分率A写了个dfs荣获40ptsbfs然后同时开一个数组\(dis\),\(dis[i][j]\)表示目前到\(i,j\)所需的最小步数若bfs时发现枚举到的状态的dis值已经小于当前位置dis值，则无需加入队列#include<bits/stdc++.h>#definelllonglong#defineullunsignedlongl......
  • 闲话8.8
    今天放假了捏，舒服早上睡到9点20......
  • 8.8《天道》观后感
    电视剧《天道》中展示了格律诗乐器的制作过程，让我们深入了解这门古老艺术的经典之道。在这篇博客中，我们将探讨格律诗乐器的生产流程及其质量控制流程，并结合软件工程专业的知识，提取出一些有启示性的经验。让我们一起走进这个古老而神奇的世界。第一部分：格律诗乐器的生产流程需求......
  • 2023.8.8 周二：replace All
    1/*2输入格式：3输入在一行中给出一句话，即一个非空字符串，由不超过1000个英文字母、数字和空格组成，以回车结束。45输出格式：6从左到右扫描输入的句子：如果句子中有超过3个连续的6，则将这串连续的6替换成9；但如果有超过9个连续的6，则将这串连续的6替换成27......
  • 8.8
    #include<cstdio>#include<cstring>#include<string>#include<math.h>#include<iostream>#include<algorithm>#include<iomanip>#include<vector>#include<map>#include<set>#include<stack>#i......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99