FJWC2019 Day2 题解
创始人
2024-05-30 08:34:34
0

T1 - 直径

思路

就类似下图的链接方法。

在这里插入图片描述

这其中每一条边权都是 111。

我们设以 222 为根的子树除去 222 有 aaa 个节点,以 333 为根的子树除去 333 有 bbb 个节点,以 444 为根的子树除去 444 有 ccc 个节点。

此时直径的数量就为 a⋅b+a⋅c+b⋅ca\cdot b+a\cdot c+b\cdot ca⋅b+a⋅c+b⋅c。

我们可以枚举 a,ba,ba,b ,看下有没有相应的 ccc 满足条件就可以了。

代码

#include 
using namespace std;
typedef long long LL;
LL k;
void out3(int a, int b, int c) {printf("%d\n", 4 + a + b + c);printf("1 2 1\n1 3 1\n1 4 1\n");for (int i = 5; i <= a + 4; i++)printf("2 %d 1\n", i);for (int i = a + 5; i <= a + 4 + b; i++)printf("3 %d 1\n", i);for (int i = a + b + 5; i <= a + 4 + b + c; i++)printf("4 %d 1\n", i);
}
int main() {// freopen("diameter.in", "r", stdin);// freopen("diameter.out", "w", stdout);scanf("%lld", &k);for (LL i = 1; i <= 5000; i++)for (LL j = 1; j <= 5000 - i; j++)if ((k - i * j) % (i + j) == 0 && (k - i * j) / (i + j) + j + i + 4 <= 5000) {out3(i, j, (k - i * j) / (i + j));return 0;}return 0;
}

T2 - 定价

思路

因为查询比较少,所以我们可以每次查询都做一次。

我们来看看如何做查询。

我们先将限制看为 000 和 111,000 代表只能选 000,111 代表 000 和 111 都能选。

我们可以从高位往低位枚举,因为我们已经知道上一个套装的选择方案了,于是我们分以下 444 类情况。

  • 如果上一位选了 111,这一位为 111,则这一位的一必须选。
  • 如果上一位选了 000,这一位为 111,则我们可以将这一位选上,更新当前套装的答案,但在再往低位枚举时就不用将这一位选上。
  • 如果上一位选了 111,这一位为 000,则我们直接退出当前套装的枚举。
  • 如果上一位选了 000,这一位为 000,则我们不用管他。

此时我们看看当前套装的答案有没有被更新过,如果没有,就说明没有一种方案满足要求,直接输出 −1-1−1 就好了。

因为这样做是 O(nm)O(nm)O(nm),我们来想想怎么优化。

因为只有为 111 的位才有贡献,所以我们可以用 set 来存每一位的限制,然后枚举时用双指针来做就可以了。

具体实现可以看代码。

注意 set 的细节,很容易越界导致gg。

代码

#include 
using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;
int n, m, q;
LL ans, sum;
set  st[1005], last, now, s;
LL Pow(LL a, int b) {LL s = 1;while (b) {if (b & 1)s = s * a % MOD;a = a * a % MOD, b = b >> 1;}return s;
}
int main() {set ::const_iterator it, jt, lt;scanf("%d%d%d", &n, &m, &q);for (int qq = 1, op, r, c; qq <= q; qq++) {scanf("%d", &op);if (op == 1) {scanf("%d%d", &r, &c);if (st[r].count(m - c))st[r].erase(m - c);elsest[r].insert(m - c);}else {last.clear();if (st[1].empty()) {printf("-1\n");continue;}last.insert(*st[1].begin());ans = Pow(2, *st[1].begin());//第一位特殊判断,直接使得第一位最小就可以了。for (int i = 2; i <= n; i++) {if (st[i].empty()) {//如果这一位没有任何1,直接为-1就可以了ans = -1;break;}jt = last.end(), jt--, it = st[i].upper_bound(*jt), sum = 0, s.clear(), now.clear();if (it == st[i].end())it--;for (; ;) {if (*jt == *it) {//上一个选了1,这一位为1now.insert(*it);if (it == st[i].begin())break;if (jt == last.begin()) {s = now;s.insert(*st[i].begin());break;}jt--, it--;}else if (*jt > *it)//上一个选了1,这一位为0break;else {//上一个选了0,这一位为1s = now;s.insert(*it);if (it == st[i].begin())break;it--;}}if (s.empty())//如果答案没有被更新过ans = -1;if (ans == -1)break;last.clear();for (it = s.begin(); it != s.end(); it++)sum = (sum + Pow(2, *it)) % MOD, last.insert(*it);(ans += sum) %= MOD;}printf("%lld\n", ans);}}return 0;
}

T3 - 排序

思路

我们可以将 cntcntcnt 次操作后能做完几个整轮,我们假设能做完 kkk 个整轮,则我们可以先将 kkk 个整轮之后的数组求出来,剩下的再暴力做。

我们来看看怎么求出 kkk 轮之后的数组。

我们先用一个优先队列存 kkk 个数,表示比当前的数小的前 kkk 个位置。

那我们做完 kkk 轮之后,当前数就会到这 k+1k+1k+1 个位置中的最后一个位置。

原理比较难讲,自己理解一下应该可以。

代码

#include 
using namespace std;
typedef long long LL;
int n, a[1000005], ans[1000005], tr[100000005], b[1000005];
LL cnt, m;
LL in() {LL s = 0;char ch = getchar();while (ch < '0' || ch > '9')ch = getchar();while (ch <= '9' && ch >= '0')s = s * 10 + ch - '0', ch = getchar();return s;
}
int main() {// freopen("sort.in", "r", stdin);// freopen("sort.out", "w", stdout);n = in(), m = cnt = in();for (int i = 1; i <= n; i++)a[i] = in(), b[a[i]] = i;priority_queue  q;int k = 1;while (m >= n - k)m = m - n + k, k++;k--;if (k) {for (int i = 1; i <= k; i++)q.push(b[i]);for (int i = k + 1; i <= n; i++) {if (q.top() > b[i])ans[q.top()] = i, q.pop(), q.push(b[i]);elseans[b[i]] = i;}for (int i = 1; i <= k; i++)ans[i] = i;}elsefor (int i = 1; i <= n; i++)ans[i] = a[i];// for (int i = 1; i <= n; i++)//     printf("%d ", ans[i]);// printf("\n");k++;for (int j = k + 1; m > 0 && j <= n; j++) {if (ans[j] < ans[k])swap(ans[j], ans[k]);m--;}for (int i = 1; i <= n; i++)printf("%d ", ans[i]);return 0;
}

相关内容

热门资讯

安卓系统可以去水印吗,轻松恢复... 你有没有遇到过这种情况:手机里下载了好多好看的视频,结果一看,哎哟,全是水印!心里那个不舒服啊,是不...
安卓系统平板看论文,安卓平板论... 你有没有想过,在安卓系统平板上阅读论文竟然可以这么酷炫?想象你手捧着一款轻薄的平板,在阳光明媚的午后...
安卓能刷pe系统,一键实现系统... 你有没有想过,你的安卓手机是不是也能来个“变身大法”,从普通模式升级到超级模式呢?没错,今天就要来聊...
安卓系统的运动数据在哪,运动数... 你有没有发现,手机里的安卓系统里藏着不少秘密呢?比如,你每天的运动数据,它们都藏在哪个角落里呢?别急...
系统miui是不是安卓系统软件... 你有没有想过,你的手机里那个熟悉的MIUI系统,它到底是不是安卓系统的一部分呢?这可是个有趣的问题,...
安卓修改系统版本骗软件,软件骗... 你知道吗?在安卓系统世界里,有时候一些小改动就能掀起大波澜。今天,就让我带你一探究竟,揭秘那些通过修...
安卓平板如何刷凤凰系统,凤凰系... 亲爱的平板用户,你是否厌倦了安卓系统的千篇一律?想要给你的平板来个焕然一新的变身?那就跟着我一起,探...
安卓手机哪款系统好,安卓手机系... 你有没有想过,你的安卓手机系统到底怎么样?是不是有时候觉得卡顿,有时候又觉得功能不够强大?别急,今天...
安卓系统qq炫舞怎么换系统,轻... 亲爱的安卓用户们,你是不是也和我一样,对QQ炫舞这款游戏爱得深沉呢?但是,有时候,我们可能会觉得系统...
安卓原生系统图案忘了,图案解锁... 亲爱的手机控们,你是否也有过这样的经历:手机屏幕上那些熟悉的安卓原生系统图案,突然间就消失得无影无踪...
安卓苹果系统版本列表,安卓与i... 你有没有发现,手机更新换代的速度简直就像坐上了火箭呢?从安卓到苹果,每个系统版本的更新都像是一场科技...
在安卓系统和网关通信,安卓系统... 在安卓系统中,网关通信是如何工作的?在当今数字化的世界里,安卓系统已经成为了智能手机和平板电脑的主流...
恢复删除的短信安卓系统,轻松找... 手机里的短信,有时候就像生活中的小确幸,记录着我们的喜怒哀乐。但你知道吗?有时候,一条重要的短信不小...
bemyeyes安卓系统,功能... 你有没有想过,如果有一款手机系统,它不仅能让你轻松管理日常事务,还能让你的手机瞬间变身成为你的私人助...
汽车怎么下载安卓系统,如何下载... 你有没有想过,你的爱车也能装上安卓系统,变成一个智能移动中心呢?没错,现在汽车界也开始流行“跨界”了...
安卓系统软件编写,功能与特性的... 你有没有想过,手机里的那些神奇应用是怎么诞生的呢?没错,就是安卓系统软件编写这个神秘的过程。今天,就...
安卓系统微信总是延迟,具体操作... 你是不是也遇到了这样的烦恼?每次打开微信,总是慢吞吞的,让人等得心焦火燎。没错,说的就是你,安卓系统...
安卓系统格式化指令,轻松掌握数... 手机里的安卓系统突然出了点小状况,是不是让你有点头疼呢?别急,今天就来给你详细说说安卓系统格式化指令...
电脑安卓系统卡嘛,安卓系统卡顿... 你有没有遇到过这种情况:手机用得正欢,突然间,安卓系统就像老牛拉车一样慢吞吞的,让人抓狂!电脑安卓系...
华为荣耀的安卓系统精简,极致体... 你有没有发现,现在的手机越来越像是一个小型的电脑了?各种功能齐全,操作复杂,有时候用起来还真是让人头...