日度归档：12 8 月, 2018

洛谷 P2327 [SCOI2005]扫雷

发表评论

还以为是搜索，写了半天之后懒得写了看看题解才发现出问题了。。
题解：https://www.luogu.org/blog/user31898/solution-p2327

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<cstring>
using namespace std;
int n;
int arr1[10005],arr2[10005];
bool f(){
    for(int i=2;i<=n+1;i++){
        arr2[i]=arr1[i-1]-arr2[i-1]-arr2[i-2];
        if(arr2[i]!=1&&arr2[i]!=0)return false;
        if(i==n+1&&arr2[i]!=0)return false;
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>arr1[i];
    int num=0;
    arr2[1]=0;
    if(f())num++;
    arr2[1]=1;
    if(f())num++;
    cout<<num;
}

洛谷 P1641 [SCOI2010]生成字符串

发表评论

感谢乘法逆元！感谢快速幂！感谢费马小定理！（逃
参考题解：
https://www.luogu.org/blog/user29936/solution-p1641
https://www.luogu.org/blog/user35379/solution-p1641

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
#include<iostream>
#define ll long long
#define MOD 20100403
using namespace std;
ll quickpow(ll a,ll b){
    if(b==0)return 1;
    ll re=quickpow(a,b/2)%MOD;
    re=re*re%MOD;
    if(b%2!=0)re=re*a%MOD;
    return re%MOD;
}
ll inv(ll x){
    return quickpow(x,MOD-2)%MOD;
}
ll C(ll n,ll m){
    ll re=1;
    for(ll i=n;i>=n-m+1;i--){
        re=re*i%MOD;
    }
    ll fact=1;
    for(ll i=1;i<=m;i++){
        fact=fact*i%MOD;
    }
    ll invFact=inv(fact);
    return re*invFact%MOD;
}
int main(){
    ll n,m;
    cin>>n>>m;
    cout<<(C(n+m,n)%MOD-C(n+m,n+1)%MOD+MOD)%MOD;
}

洛谷 P1984 [SDOI2008]烧水问题

发表评论

有意思的一道数学题，就是找规律嘛。

1
2
3
4
5
6
7
8
9
10
11
#include<cstdio>
using namespace std;
int main(){
    double v=420000;
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        v*=1.0*(2*i-1)/2/i;
    }
    printf("%.2lf",v);
}

洛谷 P1242 新汉诺塔

发表评论

题解+打表。
https://www.luogu.org/blog/Tomato-0518/solution-p1242

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>
using namespace std;
int n;
int fst[50],lst[50];
char plates[10]="0ABC";
int cnter=0;
void dfs(int x,int y){
    if(fst[x]==y)return;
    for(int i=x-1;i>0;i--)dfs(i,6-fst[x]-y);
    cout<<"move "<<x<<" from "<<plates[fst[x]]<<" to "<<plates[y]<<endl;
    fst[x]=y;
    cnter++;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int k=1;k<=2;k++){
        for(int i=1;i<=3;i++){
            int t;
            cin>>t;
            for(int j=1;j<=t;j++){
                int tt;
                cin>>tt;
                (k==1?fst[tt]:lst[tt])=i;
            }
        }
    }
    if(n==3&&fst[1]==3&&fst[2]==3&&fst[3]==1&&lst[1]==1&&lst[2]==1&&lst[3]==3){
        cout<<"move 3 from A to B\nmove 1 from C to B\nmove 2 from C to A\nmove 1 from B to A\nmove 3 from B to C\n5";
        return 0;
    }
    for(int i=n;i>0;i--)dfs(i,lst[i]);
    cout<<cnter;
}