noip2019集训测试赛（五）

小咪咪 2021-10-29 13:10 247阅读 0赞

## Problem A: lcm ##

#### Time Limit: 1000 ms Memory Limit: 256 MB ####

![mi7rsP.png][]

Sample Input
    3
    1
    2
    5
    Sample Output
    1
    4
    55

### HINT ###

对于 30% 的数据, n≤1000 .

对于 100% 的数据, t≤300000,n≤1000000 .

## Solution ##

随便推推柿子就出来了

![miHMTS.png][]

#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; int miu[1000010]; int phi[1000010]; int p[1000010]; int b[1000010]; ll e[1000010]; ll f[1000010]; int cnt; int maxn=1000000; map<int,ll> d; void init(){ memset(b,0,sizeof b); int i,j; cnt=0; for(i=2;i<=maxn;i++){ if(!b[i]){ p[++cnt]=i; miu[i]=-1; phi[i]=i-1; } for(j=1;j<=cnt&&i*p[j]<=maxn;j++){ b[i*p[j]]=1; if(i%p[j]==0){ miu[i*p[j]]=0; phi[i*p[j]]=phi[i]*p[j]; break; } miu[i*p[j]]=-miu[i]; phi[i*p[j]]=phi[i]*phi[p[j]]; } } e[1]=1; for(i=2;i<=maxn;i++) e[i]=(ll(i)*phi[i])/2; for(i=1;i<=maxn;i++) for(j=i;j<=maxn;j+=i) f[j]+=e[i]; } void solve(){ int n; scanf("%d",&n); printf("%lld\n",f[n]*n); } int main(){ init(); int t; scanf("%d",&t); while(t--) solve(); }

## Problem B: lis ##

#### Time Limit: 1000 ms Memory Limit: 128 MB ####

### Description ###

给定一个长度为 n 的序列 A=\{a1,a2,...,an\} .

问是否存在一个长度为 L 的上升子序列. 即存在 \{x1,x2,...,xL\}(x1<x2<...<xL) , 使得 ax1<ax2<...<axL .

如果不存在, 输出 `impossible` . 否则, 输出 \{ax1,ax2,...,axL\} . 若存在多组解, 输出 \{axi\} 字典序最小的一组解.

### Input ###

第一行两个数 n,L .

第二行 n 个数 a1,a2,...,an .

### Output ###

输出只有一行. 如果无解, 输出 `impossible` , 否则输出字典序最小的一组解 .

Sample Input
    4 2
    2 3 1 5
    Sample Output
    1 5

### HINT ###

对于 30% 的数据, 1≤L≤n≤10 .

对于 100% 的数据, 1≤ai≤100000,1≤L≤n≤100000 .

### Solution ###

考虑倒着处理~

先按照权值排个序，从大到小，不断加入一个维护max的数据结构

这个数据结构维护的是倒着的数组中，以某节点结束的下降子序列的最长长度

那么每次加入一个数时，我们找一下在比自己位置后的数中，下降子序列的最长长度是多少

显然这个数的下降子序列的最长长度就是刚刚查找出来的那个值+1了

最后倒着来看，我们发现倒着的下降子序列就是原数组上升子序列了

输出时按顺序遍历，贪心即可

#include<bits/stdc++.h> using namespace std; int n; int c[200001]; #define lowbit(x) x&-x void upd(int x,int w){ while(x<=n){ c[x]=max(c[x],w); x+=lowbit(x); } } int query(int x){ int ans=0; while(x){ ans=max(ans,c[x]); x-=lowbit(x); } return ans; } struct data{ int val; int id; }p[200001]; bool operator <(data a,data b){ return a.val==b.val?a.id<b.id:a.val<b.val; } int f[200001]; int main(){ int l; scanf("%d%d",&n,&l); for(int i=1;i<=n;++i){ scanf("%d",&p[i].val); p[i].id=i; } sort(p+1,p+1+n); for(int i=n;i>=1;--i){ f[i]=query(n-p[i].id+1)+1; upd(n-p[i].id+1,f[i]); //printf("%d %d\n",p[i].id,f[i]); } int maxn=0; for(int i=1;i<=n;++i)maxn=max(maxn,f[i]); if(maxn<l){ puts("impossible"); return 0; } int last=0,lpos=0; for(int i=1;i<=n&&l>=1;++i){ if(f[i]>=l&&p[i].id>lpos&&p[i].val>last){ printf("%d ",p[i].val); l--; lpos=p[i].id,last=p[i].val; } } }

## Problem C: string ##

#### Time Limit: 1000 ms Memory Limit: 256 MB ####

### Description ###

输入文件: string.in

输出文件: string.out

给定一个由且仅由字符 'H' , 'T' 构成的字符串 S .

给定一个最初为空的字符串 T , 每次随机地在 T 的末尾添加 'H' 或者 'T' .

问当 S 为 T 的后缀时, 在末尾添加字符的期望次数.

### Input ###

输入只有一行, 一个字符串 S .

### Output ###

输出只有一行, 一个数表示答案.

为了防止运算越界, 你只用将答案对 109+7 取模.

Sample Input
    HTHT
    Sample Output
    20

### HINT ###

对于 30% 的数据, |S|≤50 .

对于 100% 的数据, |S|≤1000000 .

## Solution ##

对于当前已经匹配到的第i位：

有0.5的概率在下一位填对，然后继续往下匹配

同时也有0.5的概率在下一位填错，那我们就跳回下一位的失配指针重新开始匹配，但是这样的概率我们在之前是算过的，所以我们要减去

这个失配指针可以用kmp搞出来

然后到达某一步的期望就是之前的期望总和+自己所用的2步

于是转移方程：（g\[i\]\[wrong\]即为失配指针）

\\(sum\_i=\\sum\\limits\_\{j=0\}^\{i-1\}f\_j\\)

\\(f\_i=2+sum\_\{i\}-sum\_\{g\[i\]\[wrong\]\}\\)

#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define int long long const int mod=1e9+7; int n,fail[1000001],nxt[1000001]; int sum[1000001]; char s[1000001]; signed main(){ scanf("%s",s+1); n=strlen(s+1); fail[1]=0; for(int i=1,j=0;i<=n;){ if(!j||s[i]==s[j])fail[++i]=++j; else j=fail[j]; } for(int i=1;i<=n;i++){ nxt[i]=s[fail[i]]==s[i]?nxt[fail[i]]:fail[i]; sum[i]=((sum[i-1]*2+2)%mod-sum[nxt[i]])%mod; } printf("%lld\n",sum[n]); }

转载于:https://www.cnblogs.com/youddjxd/p/11351482.html

[mi7rsP.png]: /images/20211029/3953d19ec23a4238a1fc2cf7fd26cc6c.png
[miHMTS.png]: /images/20211029/8e53e63047d84a1dbb0950acb7d64998.png