初三奥赛模拟测试5

初三奥赛模拟测试5

点击查看快读快写代码

#include <cstdio>using namespace std;
// orz laofudasuan
// modifiednamespace 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 partinline void flush () {fwrite (obuf, 1, oS - obuf, stdout);oS = obuf;}// putcharinline void putc (char x) {*oS ++ = x;if (oS == oT) flush ();}// input a signed integertemplate <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 integertemplate <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 。

\(T4\) 乘法 \(0pts\)

总结

后记

• 下发了大样例，但没有下发普通样例。
• 所有题目的 Subtask1 都是下发的大样例，但得分为 \(0pts\) 。
• \(miaomiao\) 直接把 多校冲刺 NOIP2021 (19) —「 特殊字符串·宝可梦·矩阵·乘法」 当成官方题解下发了。