更好的阅读体验
前言：
这是最戏剧性的一集，两场都是同级第一，只不过一场正数、一场倒数。
P8093 [USACO22JAN] Searching for Soulmates S
Farmer John 的每头奶牛都想找到她们的灵魂伴侣——另一头具有相似特点的奶牛，与她们最大程度地相容。每头奶牛的性格由一个整数 p i p_i pi（ 1 ≤ p i ≤ 1 0 18 1 leq p_i leq 10^{18} 1≤pi≤1018）描述。两头性格相同的奶牛就是灵魂伴侣。奶牛可以通过「改变操作」，对她的性格乘以 2 2 2，除以 2 2 2（当 p i p_i pi 是偶数时），或者加上 1 1 1。
Farmer John 最初以任意方式配对了他的奶牛。他很好奇为使每对奶牛成为灵魂伴侣需要进行多少次改变操作。对于每对奶牛，求配对中的第一头奶牛所必须进行的最小改变操作次数，从而可以与第二头奶牛成为灵魂伴侣。
输入的第一行包含 N N N（ 1 ≤ N ≤ 10 1le Nle 10 1≤N≤10），为奶牛配对的数量。以下 N N N 行每行描述了一对奶牛，包含两个整数，为她们的性格值。第一个整数是需要被改变与另一头奶牛相匹配的奶牛的性格。
输出 N N N 行。对于每一对奶牛，输出第一头奶牛需要进行的最小操作次数，使得她的性格与第二头奶牛相匹配。
6
31 13
12 8
25 6
10 24
1 1
997 120
8
3
8
3
0
20
以下除以 2 2 2操作、加 1 1 1操作、乘以 2 2 2操作分别为操作1、2、3。
思考发现，如果我们先前一直进行操作1和操作2，那等到我们再进行操作3时，就不会再进行操作1，（因为不会更优）。
换句话说，我们操作的步骤大约分为两个部分：
容易想到处理出前后半段中间的一个中间值 t t t。
由于后半段的操作不是乘以 2 2 2就是加 1 1 1，所以这个 t t t一定是 b b b的前缀（二进制中）。
那就很清晰了，直接枚举 t t t，在记录步数即可。
#include <bits/stdc++.h>
using namespace std;#define int long longint d(int x) {for (int i = 63; i >= 0; --i)if (x >> i)return i + 1;return 0;
}int get(int num, int x, int len) { return num >> (len - x); }void solve() {int a, b;scanf("%lld%lld", &a, &b);if (a == b) {puts("0");return;}int len = d(b);int ans = 0x3f3f3f3f;for (int i = 1; i <= len; i++) {int cnt = 0;int t = get(b, i, len);int ta = a;while (ta != t) {if (ta > t) {if (ta & 1)++ta;elseta /= 2;++cnt;} else {cnt += t - ta;ta = t;}}for (int j = i + 1; j <= len; j++) {t = get(b, j, len);ta <<= 1;++cnt;if (t != ta)++ta, ++cnt;}ans = min(ans, cnt);}printf("%lldn", ans);
}signed main() {int n;scanf("%lld", &n);while (n--) solve();return 0;
}
P8094 [USACO22JAN] Cow Frisbee S
Farmer John 的 N ( N ≤ 3 × 1 0 5 ) N (Nle 3times 10^5) N (N≤3×105) 头奶牛的高度为 1 , 2 , … , N 1, 2, ldots, N 1,2,…,N。一天，奶牛以某个顺序排成一行玩飞盘；令 h 1 … h N h_1 ldots h_N h1…hN 表示此顺序下奶牛们的高度（因此 h h h 是 1 … N 1 ldots N 1…N 的一个排列）。
队伍中位于位置 i i i 和 j j j 的两头奶牛可以成功地来回扔飞盘当且仅当她们之间的每头奶牛的高度都低于 min ( h i , h j ) min(h_i, h_j) min(hi,hj)。
请计算所有可以成功地来回扔飞盘的奶牛所在的位置对 i ≤ j ile j i≤j 之间的距离总和。位置 i i i 和 j j j 之间的距离为 j − i + 1 j-i+1 j−i+1。
输入的第一行包含一个整数 N N N。第二行包含 h 1 … h N h_1 ldots h_N h1…hN，用空格分隔。
输出可以成功地来回扔飞盘的奶牛所在的位置对 i ≤ j ile j i≤j 之间的距离总和。注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C 或 C++ 中的 “long long”）。
7
4 3 1 2 5 6 7
24
直接枚举、用栈维护即可。
#include <bits/stdc++.h>
using namespace std;#define int long longconst int MAXN = 3e5 + 5;int n, ans;
int h[MAXN], x[MAXN];
stack<int> s;signed main() {scanf("%lld", &n);for (int i = 1; i <= n; i++) scanf("%lld", &h[i]), x[h[i]] = i;for (int i = 1; i <= n; i++) {while (!s.empty()) {int t = s.top();ans += abs(x[h[i]] - x[t]) + 1;if (h[i] <= t)break;s.pop();}s.push(h[i]);}printf("%lldn", ans);return 0;
}
P8095 [USACO22JAN] Cereal 2 S
Farmer John 的奶牛们的早餐最爱当然是麦片了！事实上，奶牛们的胃口是如此之大，每头奶牛一顿饭可以吃掉整整一箱麦片。
最近农场收到了一份快递，内有 M M M 种不同种类的麦片（ 2 ≤ M ≤ 1 0 5 2le Mle 10^5 2≤M≤105）。不幸的是，每种麦片只有一箱！ N N N 头奶牛（ 1 ≤ N ≤ 1 0 5 1le Nle 10^5 1≤N≤105）中的每头都有她最爱的麦片和第二喜爱的麦片。给定一些可选的麦片，奶牛会执行如下的过程：
输入的第一行包含两个空格分隔的整数 N N N 和 M M M。
对于每一个 1 ≤ i ≤ N 1le ile N 1≤i≤N，第 i i i 行包含两个空格分隔的整数 f i f_i fi 和 s i s_i si（ 1 ≤ f i , s i ≤ M 1le f_i,s_ile M 1≤fi,si≤M，且 f i ≠ s i f_ineq s_i fi=si），为第 i i i 头奶牛最喜爱和第二喜爱的麦片。
输出饥饿的奶牛的最小数量，并输出任意一个可以达到此最小值的 1 … N 1ldots N 1…N 的排列。如果有多个符合要求的排列，输出任意一个。
8 10
2 1
3 4
2 3
6 5
7 8
6 7
7 5
5 8
1
1
3
2
8
4
6
5
7
对于这道题，一眼二分图最大匹配，直接匈牙利带走。
结果发现 O ( n m ) Omicron(nm) O(nm)把匈牙利带走。
但是没有关系！直接建超级源点和超级汇点，dinic网络流直接 O ( n m ) Omicron(sqrt{n}m) O(n m)带走。
但是，这样非常难打，而且在输出排队顺序是也异常繁琐，可以说是拿考场时间换代码运行时间了……
怎么办呢？还好这场比赛这道题最难，所以应该没有人会A，打点部分分也是不错的选择【大拇指d(￣▽￣)b】。
实际上这道题数据很水，匈牙利+卡常+优秀的代码逻辑是可以A的。
至于输出方案，这个想想就出来了，这里不做过多赘述。
#include <bits/stdc++.h>
using namespace std;#define int long long
#define pb push_backconst int MAXN = 2e6 + 5;int n, m;
int a[MAXN];
int f[MAXN], s[MAXN];
int lk[MAXN], ilk[MAXN];
bool vis[MAXN];
vector<int> v[MAXN], vec[MAXN];bool dfs(int x) {for (auto i : v[x]) {if (!vis[i]) {vis[i] = 1;if (!lk[i] || dfs(lk[i])) {lk[i] = x, ilk[x] = i;vis[i] = 0;return 1;}}}return 0;
}int MXMC() {int re = 0;for (int i = 1; i <= n; i++) re += dfs(i);return re;
}signed main() {scanf("%lld%lld", &n, &m);for (int i = 1; i <= n; i++) {scanf("%lld%lld", &f[i], &s[i]);v[i].pb(f[i]), v[i].pb(s[i]);vec[f[i]].pb(i);}int ans = MXMC();printf("%lldn", n - ans);queue<int> q;for (int i = 1; i <= n; i++) {if (ilk[i] != f[i])continue;printf("%lldn", i);for (auto j : vec[f[i]]) {if (ilk[j] == s[j])q.push(j);}}while (!q.empty()) {int u = q.front();q.pop();printf("%lldn", u);for (int j : vec[s[u]]) {if (ilk[j] == s[j])q.push(j);}}for (int i = 1; i <= n; i++)if (!ilk[i])printf("%lldn", i);return 0;
}
8 + 27 + 7 = 42 / r k 12 8+27+7=42/rk12 8+27+7=42/rk12
同级倒一、直接趋势。
总结发现是答题时心态没有调整好，导致陷入思维怪圈，进一步导致简单题做不对、难题不会做的情况。
原题检测，没打比赛。
一早上复习，复习了上一周打过的模拟赛。幸好我都写了总结、方便复习。
结果：
我：（开始啦开始啦！）咦？这个“旅行商简化版”是个什么东西？
隔壁的新初一：好像是我们作业里的一道题。
隔壁同级：教练，这个我们要做吗？
教练：新初三的也要做，注意一下啊。
新初三的我们：……
顺提，我们原题检测里的题，一题没A跑2圈……
但成绩挺可观的：
100 + 100 + 52 + 100 + 71 + 0 = 423 / r k 2 100+100+52+100+71+0=423/rk2 100+100+52+100+71+0=423/rk2
好吧，跑6圈。遗憾的是期望得到 500 500 500分，可惜有两题打挂了……
P9186 [USACO23OPEN] Milk Sum S
给定数组 a 1 , . . . , a N a_1,...,a_N a1,...,aN 在数组中依次选出一个元素构成排列 b 1 , . . . , b N b_1,...,b_N b1,...,bN 。定义 T = ∑ i = 1 N i × b i T = sumlimits _{i=1} ^N i times b_i T=i=1∑Ni×bi 。现在给出 Q Q Q 个操作，每个操作有两个数 x x x 和 y y y 表示将 a x a_x ax 替换成 y y y ，对于每一个操作求出操作后的 T T T 的最大值，每次操作后数组还原成原样。
5
1 10 4 2 6
3
2 1
2 8
4 5
55
81
98
容易想到肯定先排序嘛，那么就会得到新数组。
发现用二分找到查询数据在新数组位置时，答案的增加与减少可以用一个后缀和来搞定。（当然，前缀和应该没问题，可是赛时我先想到了后缀和）。
那就很容易做了，二分可以写lower_bound，减少码量。因为近期用set用得比较多，所以我就干脆丢进了set里进行lower_bound操作。
好不容易第一次赛时切绿，这里放一下我的赛时代码（无格式化、码风为本人码风）
#include<bits/stdc++.h>
using namespace std;#define int long longconst int MAXN=2e5+5,INF=1e9;int n,ans;
struct node
{int x,id;bool operator<(const node &T)const{if(x!=T.x)return x<T.x;return id<T.id;}
}a[MAXN],b[MAXN];
int sum[MAXN];
multiset<node> s;signed main()
{scanf("%lld",&n);for(int i=1;i<=n;i++){scanf("%lld",&a[i].x);b[i].x=a[i].x;b[i].id=i;}sort(a+1,a+n+1);for(int i=n;i>=1;i--){ans+=a[i].x*i;sum[i]=sum[i+1]+a[i].x;a[i].id=i;s.insert(a[i]);}s.insert({-1,0}),s.insert({INF,0});int tmp=ans,Q;scanf("%lld",&Q);while(Q--){ans=tmp;int x,y;scanf("%lld%lld",&x,&y);auto it=s.lower_bound({b[x].x,0});node t=*it;ans-=t.x*t.id;auto it2=s.upper_bound({y,0});node t2=*it2;if(t2.x==INF){ans-=sum[t.id+1];ans+=y*n;printf("%lldn",ans);continue;}if(t2.id==t.id){ans+=y*t.id;printf("%lldn",ans);continue;}if(t2.id<t.id){ans+=sum[t2.id]-sum[t.id];ans+=y*t2.id;}else{ans+=y*(t2.id-1);ans-=sum[t.id+1]-sum[t2.id];}printf("%lldn",ans);}return 0;
}
P9187 [USACO23OPEN] Field Day S
Farmer John 的 N N N 个牛棚都会选出包含 C C C 只奶牛的队伍去参加户外聚会。所有奶牛的品种都只可能是根西牛（G）或荷斯坦奶牛（H）。
我们将两个奶牛队伍中，同一位置对应的两头奶牛品种不同的所有位置 i ( 1 ≤ i ≤ C ) i(1 leq i leq C) i(1≤i≤C) 的个数，定义为的两个奶牛队伍的差异。对于编号 1... N 的每个奶牛队伍 t t t，请计算出 t t t 和其它所有队伍的差异的最大值。
第一行包含两个整数 C C C 与 N N N。
接下来 N N N 行，每行有一个长度为 C C C 的，仅包含字母 G 和 H 的字符串，每行对应一支奶牛队伍。
对于每个队伍，输出差异最大值。
第一个和第三个队伍的差异为 5 5 5。第二个和第三个队伍的差异为 3 3 3。
2 ≤ N ≤ 1 0 5 , 1 ≤ C ≤ 18 2 leq N leq 10^5,1 leq C leq 18 2≤N≤105,1≤C≤18。
5 3
GHGGH
GHHHH
HGHHG
5
3
5
这个一看就是可以转成二进制，比较就是异或操作了。
这是个很好的思路，如果赛时没想到的话那就是能力问题了。
因为他要求找最大不同，那脑海中可以有这样的思路：
最大不同 → 最小相同 → 可以对其一取反 → 最小不同 最大不同to 最小相同to 可以对其一取反to 最小不同 最大不同→最小相同→可以对其一取反→最小不同
那就很容易了，我们可以用一个非常简单的dp实现：
设 f i f_i fi为得到 i i i的最小不同，最后输出答案时就是
c − f ( 2 c − 1 ) ⊕ a i c-f_{(2^c-1) oplus a_i} c−f(2c−1)⊕ai
怎么转移呢？预处理一下就好了
#include <bits/stdc++.h>
using namespace std;#define int long longconst int MAXN = 1e6 + 5;int n, c;
int a[MAXN];
int f[MAXN];signed main() {scanf("%lld%lld", &c, &n);memset(f, 0x3f, sizeof(f));for (int i = 1; i <= n; i++) {for (int j = 1; j <= c; j++) {char ch;cin >> ch;a[i] <<= 1;a[i] += (ch == 'G');}f[a[i]] = 0;}for (int j = 1; j <= c; j++) {for (int i = 1; i <= (1 << c) - 1; i++) f[(1 << (j - 1)) ^ i] = min(f[(1 << (j - 1)) ^ i], f[i] + 1);}for (int i = 1; i <= n; i++) {int ans = c - f[((1 << c) - 1) ^ a[i]];printf("%lldn", ans);}return 0;
}
P9188 [USACO23OPEN] Pareidolia S
Farmer John有的时候看东西会忽略一些字母，如把 bqessiyexbesszieb 看成 bessiebessie。定义 B ( s ) B(s) B(s) 表示把 s s s 中的若干个字母删去后，形成尽量多个 bessie 相连的形式 (<)，返回 bessie 的最大数量。如 B ( b q e s s i y e x b e s s z i e b ) = 2 B(bqessiyexbesszieb)=2 B(bqessiyexbesszieb)=2。对字符串 s s s 计算 B ( s ) B(s) B(s) 是一个有趣的挑战，但FJ想到了一个更有趣的挑战：对 s s s 的所有子串进行计算B函数，并求和。 s s s 的长度不超过 3 ∗ 1 0 5 3*10^5 3∗105。
bessiebessie
14
abcdefghssijebessie
28
考虑DP。
设 f i f_i fi为这样一个 [ 1 , i ] [1,i] [1,i]的区间出现bessie的个数。
怎么转移呢？可以利用一下辅助数组 l s t i lst_i lsti，其中 i ∈ [ 1 , 6 ] iin [1,6] i∈[1,6]。
这是什么？
如果出现了一个序列bessie，那第 i i i位前面的bessie的起始位（b的位置）
例如bessie，那么 l s t i = 1 ( 1 ≤ i ≤ 6 ) lst_i=1 ; (1leq ileq 6) lsti=1(1≤i≤6)
那么考虑转移 f f f：
提供贡献的只有：
1情况怎么处理呢？显然是 f l s t 6 − 1 f_{lst_6-1} flst6−1
2情况呢？因为当前bessie的出现，所以对于 [ l , l s t 6 ] ( l ∈ [ 1 , l s t 6 ] ) [l,lst_6] ; (lin [1,lst_6]) [l,lst6](l∈[1,lst6])这些区间，答案都会+1，所以转移量就是 l s t 6 lst_6 lst6
综上，
f i = f l s t 6 − 1 + l s t 6 f_i=f_{lst_6-1}+lst_6 fi=flst6−1+lst6
因为答案是所有区间，所以答案就为:
∑ i = 1 n f i sum_{i=1}^n f_i i=1∑nfi
有些许改动：
（ d p i → f i dp_i to f_i dpi→fi）
（ f i → l s t i f_i to lst_i fi→lsti）
括号里左边为代码变量，右边为思路变量
#include <cstring>
#include <cstdio>
using namespace std;#define int long longconst int MAXN = 3e5 + 5;char s[MAXN];
int f[10],dp[MAXN];signed main() {scanf("%s",s+1);int n=strlen(s+1);// bessiefor(int i=1;i<=n;i++){if(s[i]=='b')f[1]=i;if(s[i]=='e')f[6]=f[5],f[2]=f[1];if(s[i]=='s')f[4]=f[3],f[3]=f[2];if(s[i]=='i')f[5]=f[4];dp[i]=dp[f[6]-1]+f[6];}int ans=0;for(int i=1;i<=n;i++)ans+=dp[i];printf("%lldn",ans);return 0;
}
100 + 25 + 17 = 142 / r k 1 100+25+17=142/rk1 100+25+17=142/rk1
这次 r k 1 rk1 rk1不只是同级，还是同机房。
再接再厉。
本文发布于:2024-02-02 14:08:20，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170685410044315.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
