2018-Multi-University-Training-hdu-Contest-9

Posted on | In , | Visitors:

嚯嚯嚯！补题！

hdu多校总链接

补题： 2+3题/11题

A. Rikka with Nash Equilibrium

果真是dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
ll mod;int n,m,sum;
ll dp[85*85][85][85];//已经占领的点的个数，行的个数，列的个数
int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d%lld",&n,&m,&mod);
        sum=n*m;
        dp[sum][n][m]=1;
        for(int k=sum-1;k>=1;k--){
            for(int i=n;i>=1;i--){
                for(int j=m;j>=1;j--){
                    if(i*j<k) break;
                    dp[k][i][j]=(ll)j*(n-i)%mod*dp[k+1][i+1][j]%mod;//占领新行
                    dp[k][i][j]+=(ll)i*(m-j)%mod*dp[k+1][i][j+1]%mod;//占领新列
                    dp[k][i][j]%=mod;
                    dp[k][i][j]+=(ll)(i*j-k)%mod*dp[k+1][i][j]%mod;//原来的行列中的
                    dp[k][i][j]%=mod;
                }
            }
        }
        
        printf("%lld\n",sum%mod*dp[1][1][1]%mod);
    }
    return 0;
}

也有找规律+大数

这个，数学好头疼！

B. Rikka with Seam

题目看了好久，真的英语不好！奇怪了，一个浙江人，想当年……可能真老了吧！

首先我们先不管“不同”，设dp[i][j]处理第i行删掉第j个位置的方案数，那么易知：

$dp[i][j]=\displaystyle \sum^{min(m,j+k)}_{p=max(1,j-k)}dp[i-1][p]$

但是对于每一行中任意一段连续的0或者连续的1，很显然删除其中的任意一个数字，最后的结果都是相同的。因此，我们可以知道：

$dp[i][j]=\displaystyle \sum^{min(m,j+k)}_{p=max(1,j-k)}dp[i-1][p]-\sum^{min(m,j+k)}_{x=max(1,j-k+1)}same[i-1][j]$

其中$same[i][j]$表示删除第i行第 j个数和删除第i行第j−1个数后得到的相同方案数

如果$str[i][j]\not= str[i][j-1]$ 那么$same[i][j]$=0

否则，对于第j 个和第j−1个的转移区间分别为[j−k,j+k]，[j−1−k,j−1+k]，那么它们的交叉区间为[j−k,j−1+k]，则从该区间内转移得到的方案数会重复计算一次,因此有：

$same[i][j]=\displaystyle \sum^{min(m,j+k-1)}_{p=max(1,j-k)}dp[i-1][p]-\sum^{min(m,j+k-1)}_{x=max(j-k)}same[i-1][x]$

我们可以用前缀和优化至o(n^2)；同时我们可以用滚动数组，节省空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
const int mod=998244353;
const int maxn=2e3+10;
char str[maxn][maxn];
int same[2][maxn],dp[2][maxn];
int n,m,k,l,r;
int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=n;i++){
            str[i][0]='2';//方便后面处理same
            scanf("%s",str[i]+1);
        }
        
        for(int i=1;i<=m;i++){
            dp[0][i]=1;
            same[0][i]=(str[1][i]==str[1][i-1]);
        }
        
        int pre=0,now=1;
        for(int i=2;i<=n;i++){            
            for(int j=1;j<=m;j++){
                dp[pre][j]=(dp[pre][j-1]+dp[pre][j])%mod;
                same[pre][j]=(same[pre][j-1]+same[pre][j])%mod;
            }
            
            for(int j=1;j<=m;j++){
                l=max(1,j-k);r=min(m,j+k);
                dp[now][j]=(dp[pre][r]-dp[pre][l-1]+mod)%mod;
                dp[now][j]=(dp[now][j]-(same[pre][r]-same[pre][l]+mod)%mod+mod)%mod;
                if(str[i][j]!=str[i][j-1]){
                    same[now][j]=0;
                    continue;
                }
                r=min(m,j+k-1);
                same[now][j]=(dp[pre][r]-dp[pre][l-1]+mod)%mod;
                same[now][j]=(same[now][j]-(same[pre][r]-same[pre][l]+mod)%mod+mod)%mod;
            }
            swap(now, pre);
        }
        ll ans=dp[pre][1]%mod;
        for(int i=2;i<=m;i++){
            ans=(ans+dp[pre][i]-same[pre][i]+mod)%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

D. Rikka with Stone-Paper-Scissors

看到19的时候，疙瘩了一下，然后就开始找这些数字是19的倍数的关系；然后就发现了下面的规律

同时，又知道石头剪刀布是很公平的；然后……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
typedef long long ll;
ll __gcd(ll a,ll b){
    return b?__gcd(b, a%b):a;
}
int main(){
//    cout<<3552.0/19<<endl;
//    int sum=1368;
//    cout<<1.0*(123*(200-1068)+456*(1068-100)+789*(100-200))/sum<<endl;
    int T;scanf("%d",&T);
    ll a,b,c,aa,bb,cc;
    while(T--){
        scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&aa,&bb,&cc);
        ll sum=(a+b+c);
        ll tmp=(a*(bb-cc)+b*(cc-aa)+c*(aa-bb));
        int sign=tmp<0?-1:1;
        tmp=abs(tmp);
        if(sign==-1) printf("-");
        ll gcd=__gcd(sum,tmp);
        sum/=gcd;
        tmp/=gcd;
        if(sum==1) printf("%lld\n",tmp);
        else printf("%lld/%lld\n",tmp,sum);
    }
    return 0;
}

J. Rikka with Time Complexity

终终于，今天看了好多数学就头疼了……

写一下过程

1
2
我们假设每一个都含有3个长度的，若不足的话，我们把那一位置成INF，这样他的值近似于1；
然后我们来化简式子：

$log_{f(A1)}g(A)=f(A2)^{f(A3)}$

$\frac{log_2 g(A)}{log_2 f(A1)}=f(A2)^{f(A3)}$

$log_{f(A2)}\frac{log_2 g(A)}{log_2 f(A1)}=f(A3)$

$log_{f(A2)}log_2g(A)-log_{f(A2)}log_2f(A1)=f(A3)$

$\frac{log_2log_2g(A)-log_2log_2f(A1)}{log_2 f(A2)}=f(A3)$

$log_2log_2g(A)-log_2log_2f(A1)=f(A3)*f(A2+1)$

$log_2log_2g(A)=f(A1+2)+f(A3)*f(A2+1)$

$lim_{n->+∞}\frac{g(A)}{g(B)}=lim_{n->+∞}\frac{log_2log_2g(A)}{log2_log2g(B)}$

所以就是$f(A1+2)+f(A3)*f(A2+1)$的比较了

再化简一下就是$f(A1+2)f(INF)+f(A3)f(A2+1)$

A的数越小，值越大

然后比较的时候，由于log的形式，所以可以通过先比较最小值；若相同，再比较最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll INF=1e9+10;
pair<ll, ll>a1,a2,b1,b2;
ll a[5],b[5];
int n,m;
int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<3;i++) a[i]=b[i]=INF;
        for(int i=0;i<n;i++) scanf("%lld",&a[i]);
        for(int i=0;i<m;i++) scanf("%lld",&b[i]);
        a1=make_pair(a[0]+2, INF);a2=make_pair(a[1]+1, a[2]);
        b1=make_pair(b[0]+2, INF);b2=make_pair(b[1]+1, b[2]);
        if(a1.first>a1.second) swap(a1.first, a1.second);
        if(a2.first>a2.second) swap(a2.first, a2.second);
        if(b1.first>b1.second) swap(b1.first, b1.second);
        if(b2.first>b2.second) swap(b2.first, b2.second);
        if(a1>a2)swap(a1,a2);
        if(b1>b2)swap(b1,b2);
        
        if(a1<b1) printf("1\n");
        else if(a1>b1) printf("-1\n");
        else if(a2<b2) printf("1\n");
        else if(a2>b2) printf("-1\n");
        else printf("0\n");
    }
    return 0;
}

K. Rikka with Badminton

刚开始题目理解错了，以为每一对都需要一副球拍和一个球；后来博博告诉我，每个人拥有的东西都是负数啊，所以我就开始分类讨论了

1
2
3
4
b=0	 c=n d=0 a=n
     c=n d=1 a=n
b=1  c=n d=0 a=n
b>=2 c=0 d=0 a=n

$ans=2^c2^a+C_d^12^c2^a+C_b^12^c2^a+\displaystyle \sum_{i=2}^b (C_b^i2^a)$

由二项式定理可知

$C_n^0+C_n^1+\cdot\cdot\cdot+C_n^n=2^n$

化简可得

$ans=2^{c+a}(1+d+b)+2^a(2^b-C_b^1-C_b^0)=2^{c+a}(1+d+b)+2^a(2^b-b-1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll Pow(ll a, int b, int p) {
    a%=p; ll ans=1;
    for(; b; b>>=1, a=a*a%p)
        if(b&1) ans=ans*a%p;
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        ll t1 = ((Pow(2, a+c, mod) * (1+b+d) + Pow(2, a, mod) * (Pow(2, b, mod) - b - 1)) % mod + mod) % mod;
        cout << t1 << endl;
    }    
}

碎碎念

2018.08.22 早

刷了好久的六级成绩

就明白的是为什么每次写作那么低

真的是老师说的我的作文不适合应试么！！！

2018.08.22 晚

我真的觉得我今天头大了

数学数学数学！！！！！！

啊啊啊啊啊啊啊啊啊啊啊啊啊啊！！！！1

2018.08.23 午

又是一天宅

临近开学，越来越懒了！

明天貌似有漫威电影(-.-)

不出门不出门不出门！！！！！

转载请注明出处，谢谢。

愿 我是你的小太阳


买糖果去喽