2019杭電多校(第二場)
1005 Everything Is Generatoed In Equal Probability(数学)
http://acm.hdu.edu.cn/showproblem.php?pid=6595
題意
期待する
Nを一つあげます 問1−Nでランダムに1つの数を選択し、ランダムに1−nを並べて逆の順を求める.その後、サブシーケンスをランダムに選択して逆の順を求める.
考え方
n個の数がそろっている逆順は、希望個数に対して(n*(n-1)/4 全部でn*(n-1)/2が逆順で期待されるのは1/2です.
dp[i]は配列長iの後継期待である.
dp[i]=(n*(n-1)/4+dp[i]*C[0]/pow(2,n)+ Σdp[i]*C[i]、[n]/pow(2,n)
dp[i]=(n(n-1)/4+ Σdp[i]*C[i]/pow(2,n)*pow(2,n)/(pow(2,n)-1
Nに対してdp 1−nの和を計算し、Nで割る.
コード
http://acm.hdu.edu.cn/showproblem.php?pid=6599
題意
リターンツリー
長さnの文字列をあげます.
自分のために回文串の前半も回文串の数です.
考え方
前半は回文だから、後半も回文列に違いない.
回文樹のfailは現在の最後の最長の回文列を指します.どのように回文列のfailポインタが指す回文列の長さですか?それとも前の長さを続けて彼の半分が存在します.彼は要求に合う回文列です.
再帰的に長さの半分を探すとタイムアウトします.failポインタの方向に沿ってDFSを走る木を作ってもいいです.
コード
http://acm.hdu.edu.cn/showproblem.php?pid=6600
題意
数nをあげます.何回か聞いてみます.毎回数mを教えてください.n^mがmに等しいかどうか教えてくれます.
最適解を聞いた場合に尋ねる方案数
考え方
最適解とは、順番に各案の数を聞くことです.膜数は1 e 6+3で、1 e 6+3より大きい木は0です.
コード
http://acm.hdu.edu.cn/showproblem.php?pid=6601
題意
n個の数mをあげます.毎回区間l-rの間で最大三角形の面積ができますか?
考え方
最も不成三角形の最適な状況はフィボナッチ数列で、区間の長さが40より大きいことが分かります.
問題は区間の第kの大きいsortがきっとタイムアウトします.主席の木を使うことができます.
コード
http://acm.hdu.edu.cn/showproblem.php?pid=6602
題意
c kとnの数をあげます.条件を満たす一番長い区間の長さを求めます.
条件 各数の個数>=kまたは0
考え方
列挙の各右端点を求めます.各左端点1-cの中で条件を満たす個数はどれぐらいですか?左端がcの点です.
コード
http://acm.hdu.edu.cn/showproblem.php?pid=6595
題意
期待する
Nを一つあげます 問1−Nでランダムに1つの数を選択し、ランダムに1−nを並べて逆の順を求める.その後、サブシーケンスをランダムに選択して逆の順を求める.
考え方
n個の数がそろっている逆順は、希望個数に対して(n*(n-1)/4 全部でn*(n-1)/2が逆順で期待されるのは1/2です.
dp[i]は配列長iの後継期待である.
dp[i]=(n*(n-1)/4+dp[i]*C[0]/pow(2,n)+ Σdp[i]*C[i]、[n]/pow(2,n)
dp[i]=(n(n-1)/4+ Σdp[i]*C[i]/pow(2,n)*pow(2,n)/(pow(2,n)-1
Nに対してdp 1−nの和を計算し、Nで割る.
コード
#include
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll C[3300][3300];
ll dp[3300];
ll q[3300];
ll qw[3300];
ll qw2[3300];
ll qsort(ll x,ll n)
{
ll ans = 1;
while(n)
{
if(n % 2 == 1)
{
ans = (ans * x) % mod;
}
x = (x * x) % mod;
n /= 2;
}
ans %= mod;
return ans;
}
void ok()
{
ll xx = 1;
for(ll i = 1;i <= 3000;i++)
{
xx *= 2;
xx %= mod;
q[i] = xx;
qw[i] = qsort(xx,mod-2);
qw2[i] = qsort(xx-1,mod-2);
}
dp[0] = 0;
dp[1] = 0;
ll qwe = qsort(4,mod-2);
for(ll i = 2;i <= 3000;i++)
{
dp[i] = (i*(i-1)*qwe)%mod;
for(ll j = 1;j < i;j++)
{
dp[i] = (dp[i] + ((C[i][j]*dp[j])%mod)*qw[i])%mod;
}
dp[i] = ((dp[i]*q[i])%mod*(qw2[i]))%mod;
}
}
void cc(ll n)
{
for(ll i=0;i<=n;i++)
C[i][0]=1;
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=i;j++)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
}
int main()
{
ll n;
cc(3002);
ok();
while(scanf("%lld",&n)!= EOF)
{
ll ans = 0;
for(ll i = 2;i <= n;i++)
{
ans = (ans + dp[i]) % mod;
}
ans = (ans * qsort(n,mod-2))%mod;
printf("%lld
",ans);
}
return 0;
} http://acm.hdu.edu.cn/showproblem.php?pid=6599
題意
リターンツリー
長さnの文字列をあげます.
自分のために回文串の前半も回文串の数です.
考え方
前半は回文だから、後半も回文列に違いない.
回文樹のfailは現在の最後の最長の回文列を指します.どのように回文列のfailポインタが指す回文列の長さですか?それとも前の長さを続けて彼の半分が存在します.彼は要求に合う回文列です.
再帰的に長さの半分を探すとタイムアウトします.failポインタの方向に沿ってDFSを走る木を作ってもいいです.
コード
#include
using namespace std;
const int MAXN = 310005 ;
const int N = 26 ;
struct Palindromic_Tree {
int next[MAXN][N] ;//next ，next ，
int fail[MAXN] ;//fail ， fail
long long cnt[MAXN] ;
//cnt[i] i （ ， count() ）
int num[MAXN] ; //num[i] i
int len[MAXN] ;//len[i] i
int S[MAXN] ;//
int last ;// ， add
int n ;//
int p ;//
vector to[MAXN]; //
int newnode ( int l ) {//
for ( int i = 0 ; i < N ; ++ i ) next[p][i] = 0 ;
cnt[p] = 0 ;
num[p] = 0 ;
len[p] = l ;
return p ++ ;
}
void init () {//
p = 0 ;
newnode (0) ;
newnode (-1) ;
last = 0 ;
n = 0 ;
S[n] = -1 ;// ，
fail[0] = 1 ;
to[1].push_back(0);
}
int get_fail ( int x ) {// KMP ，
while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ;
return x ;
}
void add ( int c ) {
c -= 'a';
S[++ n] = c ;
// cout<= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
// cnt， fail[v]=u， u v ！
}
} ;
Palindromic_Tree A;
char s[MAXN];
int vis[MAXN],ans[MAXN];
void dfs(int u)
{
if(vis[(A.len[u]+1) / 2] == 1) ans[A.len[u]] += A.cnt[u];
if(A.len[u] >= 0) vis[A.len[u]] = 1;
for(int i = 0;i < A.to[u].size();i++)
{
int v = A.to[u][i];
dfs(v);
}
if(A.len[u] >= 0) vis[A.len[u]] = 0;
}
int main()
{
while(scanf("%s",s ) != EOF)
{
int n = strlen(s);
for(int i = 0;i <= n;i++)
{
A.to[i].clear();
}
memset(ans,0,sizeof(ans));
A.init();
for(int i =0;i < n;i++)
{
A.add(s[i]);
}
A.count();
dfs(1);
ans[1] = n;
for(int i = 1;i <= n;i++)
{
if(i!= 1) printf(" ");
printf("%d",ans[i]);
}
printf("
");
}
} http://acm.hdu.edu.cn/showproblem.php?pid=6600
題意
数nをあげます.何回か聞いてみます.毎回数mを教えてください.n^mがmに等しいかどうか教えてくれます.
最適解を聞いた場合に尋ねる方案数
考え方
最適解とは、順番に各案の数を聞くことです.膜数は1 e 6+3で、1 e 6+3より大きい木は0です.
コード
#include
#define ll long long
#define mod 1000003
#define inf 0x3f3f3f3f
using namespace std;
int main()
{
ll n;
while(~scanf("%lld",&n))
{
ll ans=1;
if(n>=mod)
{
printf("0
");
continue;
}
for(ll i=1; i<=n; i++)
ans=(ans*i)%mod;
printf("%lld
",ans);
}
return 0;
}
http://acm.hdu.edu.cn/showproblem.php?pid=6601
題意
n個の数mをあげます.毎回区間l-rの間で最大三角形の面積ができますか?
考え方
最も不成三角形の最適な状況はフィボナッチ数列で、区間の長さが40より大きいことが分かります.
問題は区間の第kの大きいsortがきっとタイムアウトします.主席の木を使うことができます.
コード
#include
#include
#define ll long long
#include
#include
using namespace std;
const ll MAX = 112345;
struct Node
{
ll sum, l, r;
} tree[MAX * 40];
ll root[MAX], cnt;
ll data[MAX];
vector sorted;
// ID
ll get_id(ll x)
{
return lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin() + 1;
}
void init()
{
cnt = 0;
root[0] = 0;
}
//
ll create_node(ll po)
{
ll idx = ++cnt;
tree[idx].sum = tree[po].sum + 1;
tree[idx].l = tree[po].l;
tree[idx].r = tree[po].r;
return idx;
}
void updata(ll &o, ll po, ll l, ll r, ll pos)
{
o = create_node(po);
if (l == r) return;
ll m = (l + r) >> 1;
if (pos <= m) updata(tree[o].l, tree[po].l, l, m, pos);
else updata(tree[o].r, tree[po].r, m + 1, r, pos);
}
//
ll query(ll s, ll e, ll l, ll r, ll k)
{
if (l == r) return l;
ll m = (l + r) >> 1;
ll sum = tree[tree[e].l].sum - tree[tree[s].l].sum;
if (k <= sum) return query(tree[s].l, tree[e].l, l, m, k);
else return query(tree[s].r, tree[e].r, m + 1, r, k - sum);
}
int main()
{
ll n, m;
while (~scanf("%lld %lld", &n, &m))
{
init();
for (ll i = 1; i <= n; i++)
{
scanf("%lld", &data[i]);
sorted.push_back(data[i]);
}
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
ll num = sorted.size();
for (ll i = 1; i <= n; i++)
updata(root[i], root[i - 1], 1, num, get_id(data[i]));
for(ll i=0; ic)
{
ans=a+b+c;
break;
}
}
printf("%lld
",ans);
}
}
return 0;
} http://acm.hdu.edu.cn/showproblem.php?pid=6602
題意
c kとnの数をあげます.条件を満たす一番長い区間の長さを求めます.
条件 各数の個数>=kまたは0
考え方
列挙の各右端点を求めます.各左端点1-cの中で条件を満たす個数はどれぐらいですか?左端がcの点です.
コード
#include
using namespace std;
const int MAXN = 100005;
struct node
{
int data,lazy;
}tree[MAXN*4];
int a[MAXN];
int n,c,k;
vector q[MAXN];
int maxn,qw;
void build(int x,int l,int r)
{
tree[x].data = 0;
tree[x].lazy = 0;
if(l==r) return ;
int mid = (l + r) / 2;
build(x*2,l,mid);
build(x*2+1,mid+1,r);
}
void pushdown(int rt)
{
if(tree[rt].lazy)
{
tree[rt*2].lazy += tree[rt].lazy;
tree[rt*2+1].lazy += tree[rt].lazy;
tree[rt*2].data += tree[rt].lazy;
tree[rt*2+1].data += tree[rt].lazy;
tree[rt].lazy = 0;
}
}
void updata(int l,int r,int rt,int L,int R,int x)
{
if(l > r) return ;
if(l == L&&r == R)
{
tree[rt].data += x;
tree[rt].lazy += x;
return ;
}
pushdown(rt);
int mid = (L + R) / 2;
if(mid >= r)
{
updata(l,r,rt*2,L,mid,x);
tree[rt].data = max(tree[rt*2].data,tree[rt*2+1].data);
}
else if(mid < l)
{
updata(l,r,rt*2+1,mid+1,R,x);
tree[rt].data = max(tree[rt*2].data,tree[rt*2+1].data);
}
else
{
updata(l,mid,rt*2,L,mid,x);
updata(mid+1,r,rt*2+1,mid+1,R,x);
tree[rt].data = max(tree[rt*2].data,tree[rt*2+1].data);
}
}
void query(int l,int r,int rt,int L,int R)
{
if(L==R)
{
if(tree[rt].data == c) qw = L;
return ;
}
pushdown(rt);
int mid = (L + R ) / 2;
if(mid >= r)
{
if(tree[rt*2].data >= c) query(l,mid,rt*2,L,mid);
}
else if(mid < l)
{
if(tree[rt*2+1].data >= c) query(l,mid,rt*2+1,mid+1,R);
}
else
{
if(tree[rt*2].data >= c) query(l,mid,rt*2,L,mid);
else if(tree[rt*2+1].data >= c) query(mid+1,r,rt*2+1,mid+1,R);
}
}
int main()
{
// freopen("in.txt","r",stdin);
while(scanf("%d%d%d",&n,&c,&k) != EOF)
{
for(int i = 1;i <= n;i++)
{
scanf("%d",&a[i]);
}
for(int i = 1;i <= c;i++)
{
q[i].clear();
q[i].push_back(0);
}
int ans=0;
build(1,1,n);
for(int i = 1;i <= n;i++)
{
int x = a[i];
q[x].push_back(i);
int siz = q[x].size();
if(siz > k)
{
int l = q[x][siz-k-1]+1,r = q[x][siz-k];
updata(l,r,1,1,n,1);
}
int l = q[x][siz-2]+1,r = i-1;
updata(l,r,1,1,n,-1);
updata(i,i,1,1,n,c-1);
qw = 0;
query(1,i,1,1,n);
if(qw != 0)
{
ans = max(i-qw+1,ans);
}
}
printf("%d
",ans);
}
return 0;
}