初三奥赛模拟测试5
点击查看快读快写代码
#include <cstdio>
using namespace std;
// orz laofudasuan
// modified
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
template <class I>
inline void gi (I &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
// print a signed integer
template <class I>
inline void print (I x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: gi;
using io :: putc;
using io :: print;
int v;
int main () {
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
gi (v);
print (v);
putc ('\n');
}
\(T1\) 特殊字符串 \(0pts\)
-
设 \(f_{i}\) 表示以 \(i\) 为结尾的子序列的最大奇异值，状态转移方程为 \(f_{i}=\max\limits_{j=a}^{z} \{ f_{pos_{j}}+k_{t=js_{i}} \}\) ，其中 \(pos_{j}\) 表示 \(1 \sim i\) 中 \(j\) 最后的出现位置。
-
注意可能会出现 \(p_{i}\) 相同，但 \(k_{i}\) 不同的情况。
点击查看代码
ll f[100010],pos[30]; char s[100010]; string t; map<string,ll>g; ll val(char x) { return x-'a'+1; } int main() { freopen("shiki.in","r",stdin); freopen("shiki.out","w",stdout); ll n,m,k,ans=0,i,j; char pd; cin>>n>>(s+1)>>m; for(i=1;i<=m;i++) { cin>>pd; t=' '; t+=pd; cin>>pd; t+=pd; cin>>; g[t]+=k; } for(i=1;i<=n;i++) { for(pd='a';pd<='z';pd++) { if(pos[val(pd)]!=0) { t=' '; t+=pd; t+=s[i]; f[i]=max(f[i],f[pos[val(pd)]]+g[t]); } } pos[val(s[i])]=i; ans=max(ans,f[i]); } cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; }
\(T2\) 宝可梦 \(0pts\)
\(T3\) 矩阵 \(0pts\)
- 部分分
- \(0pts\) ：输出
-1。
- \(0pts\) ：输出
\(T4\) 乘法 \(0pts\)
总结
后记
- 下发了大样例，但没有下发普通样例。
- 所有题目的
Subtask1都是下发的大样例，但得分为 \(0pts\) 。 - \(miaomiao\) 直接把 多校冲刺 NOIP2021 (19) —「 特殊字符串·宝可梦·矩阵·乘法」 当成官方题解下发了。