Chengrui's Blog

0%

发表于 分类于 ， Disqus：

对每块蛋糕进行统计，若有1颗就直接返回1，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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=25;
int n,m;
int d[maxn][maxn][maxn][maxn];
bool g[maxn][maxn];
int getnum(int u,int d,int l,int r){
    bool flag=false;
    for(int i=u;i<=d;++i)
        for(int j=l;j<=r;++j)
            if(g[i][j]){
                if(flag) return 2;
                else flag=true;
            }
    return flag;
}
int dp(int u,int dd,int l,int r){
    int& k=d[u][dd][l][r];
    if(k!=-1) return k;
    int num=getnum(u,dd,l,r);
    if(num==1) return 0;
    if(!num) return inf;
    k=inf;
    for(int i=l;i<r;++i)
        k=min(k,dp(u,dd,l,i)+dp(u,dd,i+1,r)+dd-u+1);
    for(int i=u;i<dd;++i)
        k=min(k,dp(u,i,l,r)+dp(i+1,dd,l,r)+r-l+1);
    return k;
}
int main(){
    int k,t=0;
    while(~scanf("%d%d%d",&n,&m,&k)){
        memset(g,0,sizeof(g));
        memset(d,-1,sizeof(d));
        while(k--){
            int r,c;
            scanf("%d%d",&r,&c);
            g[r][c]=true;
        }
        printf("Case %d: %d\n",++t,dp(1,n,1,m));
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出两个序列，要求合并后的序列的子序列包含所给序列，为合并后序列的最短长度和有几种合并方式可以合并出最短序列。类似于求公共子序列的方法，具体转移方程见代码。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=35;
int l[maxn][maxn],d[maxn][maxn];
char s1[maxn],s2[maxn];
int main(){
    int t,tt=0;scanf("%d%*c",&t);
    while(t--){
        memset(l,0,sizeof(l));
        memset(d,0,sizeof(d));
        for(int i=0;i<maxn;++i){
            l[i][0]=l[0][i]=i;
            d[i][0]=d[0][i]=1;
        }
        gets(s1+1);
        gets(s2+1);
        int l1=(int)strlen(s1+1),l2=(int)strlen(s2+1);
        for(int i=1;i<=l1;++i){
            for(int j=1;j<=l2;++j){
                if(s1[i]==s2[j]){
                    l[i][j]=l[i-1][j-1]+1;
                    d[i][j]=d[i-1][j-1];
                }
                else{
                    if(l[i-1][j]>l[i][j-1]){
                        l[i][j]=l[i][j-1]+1;
                        d[i][j]=d[i][j-1];
                    }
                    else if(l[i-1][j]<l[i][j-1]){
                        l[i][j]=l[i-1][j]+1;
                        d[i][j]=d[i-1][j];
                    }
                    else{
                        l[i][j]=l[i][j-1]+1;
                        d[i][j]=d[i-1][j]+d[i][j-1];
                    }
                }
            }
        }
        printf("Case #%d: %d %d\n",++tt,l[l1][l2],d[l1][l2]);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

首先枚举所有 a ，然后利用扩展欧几里得算法求出 b 。之后进行验证。

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
#include<cstdio>
typedef long long LL;
using namespace std;
const int maxn=210;
LL x[maxn];
void exgcd(LL a,LL b,LL& d,LL& x,LL& y){
    if(!b) d=a,x=1,y=0;
    else exgcd(b,a%b,d,y,x),y-=x*(a/b);
}
int main(){
    int t;scanf("%d",&t);
    for(int i=0;i<t;++i) scanf("%lld",&x[2*i]);
    t<<=1;
    for(LL a=0;;++a){
        LL k,b,d,tmp=x[2]-a*a*x[0];
        exgcd(10001,a+1,d,k,b);
        if(tmp%d) continue;
        b=b*tmp/d;
        bool flag=true;
        for(int i=1;i<t;++i){
            if(i&1) x[i]=(a*x[i-1]+b)%10001;
            else {
                if(x[i]!=(a*x[i-1]+b)%10001){
                    flag=false;
                    break;
                }
            }
        }
        if(flag) break;
    }
    t>>=1;
    for(int i=0;i<t;++i)
        printf("%lld\n",x[2*i+1]);
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

计算第 a b 个斐波那契数对 n 取模的值。对不同的 n 取模，最长 n 2 就会出现循环。首先预处理计算所有可能的值，然后对每个输入快速幂取模找在周期中的位置输出。数据大必须用unsigned long long。

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
#include<cstdio>
#include<vector>
using namespace std;
typedef unsigned long long LLU;
const int maxn=1010;
vector<int> f[maxn];
void init(){
    for(int i=2;i<maxn;++i){
        f[i].push_back(0);
        f[i].push_back(1%i);
        for(int j=2;;++j){
            f[i].push_back((f[i][j-1]+f[i][j-2])%i);
            if(f[i][j-1]==0&&f[i][j]==1) break;
        }
        f[i].pop_back(),f[i].pop_back();
    }
    return;
}
LLU modexp(LLU a,LLU b,LLU mod){
    LLU cur=1,tmp=a;
    while(b){
        if(b&1) cur=cur*tmp%mod;
        tmp=tmp*tmp%mod;
        b>>=1;
    }
    return cur;

}
int main(){
    init();
    int t;scanf("%d",&t);
    while(t--){
        LLU a,b,n;
        scanf("%llu%llu%llu",&a,&b,&n);
        LLU k=LLU(f[n].size());
        printf("%d\n",k?f[n][modexp(a%k,b,k)]:0);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出n只筷子，找出 k + 8 组，每组三根，输出每组最短两根长度差的平方和的最小值。
倒序读入，对每个可以选的点位有两种转移状态。
DP数组滚动使用，节约空间和初始化时间。
状态转移方程： d [ i ] [ j ] = m i n ( d [ i − 1 ] [ j ] , d [ i − 2 ] [ j − 1 ] + ( a [ i ] − a [ i − 1 ] ) 2 )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=5010;
int a[maxn],d[3][maxn];
int main(){
    int t;scanf("%d",&t);
    while(t--){
        int k,n;scanf("%d%d",&k,&n);
        k+=8;
        memset(d,0x3f,sizeof(d));
        for(int i=n;i>=1;--i)
            scanf("%d",&a[i]);
        d[0][0]=d[1][0]=d[2][0]=0;
        for(int i=3;i<=n;++i)
            for(int j=1;j*3<=i;++j)
                d[i%3][j]=min(d[(i-1)%3][j],d[(i-2)%3][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]));
        printf("%d\n",d[n%3][k]);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

d [ u ] [ 1 ] 和 d [ u ] [ 0 ] 分别表示选结点u和不选结点u在它的子树中最大的数目， f [ u ] [ t ] 表示相应选法的唯一性。
d [ u ] [ 1 ] = s u m { d [ v ] [ 0 ] } ， d [ u ] [ 0 ] = s u m { m a x ( d [ v ] [ 0 ] , d [ v ] [ 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
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
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<map>
using namespace std;
const int maxn=210;
map<string,int> id;
int d[maxn][2];
bool f[maxn][2];
vector<int> sons[maxn];
int dp(int u,int t){
    int& k=d[u][t]=t;
    if(sons[u].empty()) return k;
    if(t==1){
        for(int i=0;i<(int)sons[u].size();++i){
            k+=dp(sons[u][i],0);
            if(f[sons[u][i]][0]!=1)
                f[u][1]=false;
        }
    }
    else {
        for(int i=0;i<(int)sons[u].size();++i){
            int s=sons[u][i],a=dp(s,0),b=dp(s,1);
            k+=max(a,b);
            if(a==b||(a>b&&!f[s][0])||(a<b&&!f[s][1]))
                f[u][0]=false;
        }
    }
    return k;
}
int main(){
    int n;
    while(cin>>n&&n){
        id.clear();
        memset(d,0,sizeof(d));
        memset(f,1,sizeof(f));
        for(int i=0;i<maxn;++i) sons[i].clear();
        string s;cin>>s;
        int cnt=0;
        id[s]=cnt++;
        for(int i=2;i<=n;++i){
            cin>>s;
            if(!id.count(s)) id[s]=cnt++;
            int k=id[s];
            cin>>s;
            if(!id.count(s)) id[s]=cnt++;
            sons[id[s]].push_back(k);
        }
        int a=dp(0,0),b=dp(0,1);
        bool unk=true;
        if(a==b||(a>b&&!f[0][0])||(a<b&&!f[0][1])) unk=false;
        printf("%d %s\n",max(a,b),unk?"Yes":"No");
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

书上给出了思路和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
31
32
33
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=100010;
int n,t;
vector<int> sons[maxn];
int dp(int u){
    if(sons[u].empty()) return 1;
    int k=(int)sons[u].size();
    vector<int> d;
    for(int i=0;i<k;++i)
        d.push_back(dp(sons[u][i]));
    sort(d.begin(),d.end());
    int c=(k*t-1)/100+1;
    int ans=0;
    for(int i=0;i<c;++i)
        ans+=d[i];
    return ans;
}
int main(){
    while(~scanf("%d%d",&n,&t)){
        if(!n&&!t) break;
        for(int i=0;i<=n;++i) sons[i].clear();
        for(int i=1;i<=n;++i){
            int k;
            scanf("%d",&k);
            sons[k].push_back(i);
        }
        printf("%d\n",dp(0));
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出一个 n 、 m 、 k ，生成一个序列。问其中包含1到k所有正整数的最短连续子序列的长度。
序列生成方式：
x 1 = 1 , x 2 = 2 , x 3 = 3 , x i = ( x i − 1 + x i − 2 + x i − 3 ) % m + 1
利用尺取法可以在 O ( n ) 时间内解决。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000010;
int n,m,k;
int a[maxn]={0,1,2,3},vis[maxn];
int main(){
    int t,tt=0;scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&k);
        memset(vis,0,sizeof(vis));
        for(int i=4;i<=n;++i)
            a[i]=(a[i-1]+a[i-2]+a[i-3])%m+1;
        int ans=0x3f3f3f3f,s=1,e=1,cnt=0;
        for(;;){
            while(e<=n&&cnt<k){
                vis[a[e]]++;
                if(a[e]<=k&&vis[a[e]]==1) ++cnt;
                ++e;
            }
            if(cnt<k) break;
            ans=min(e-s,ans);
            vis[a[s]]--;
            if(a[s]<=k&&vis[a[s]]==0) --cnt;
            ++s;
        }
        printf("Case %d: ",++tt);
        if(ans==0x3f3f3f3f) printf("sequence nai\n");
        else printf("%d\n",ans);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出一段播放记录，判断下次随机开始的地方有几种不同情况。
首先利用滑动窗口判断当前位置的前 s 个位置数字是否均不同。
然后枚举终点，每次进行验证。

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
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=200010;
int a[maxn];
int vis[maxn];
bool ok[maxn];
int main(){
    int t;scanf("%d",&t);
    while(t--){
        int s,n,cnt=0,ans=0,ns;
        scanf("%d%d",&s,&n);
        memset(a,0,sizeof(a));
        memset(ok,0,sizeof(ok));
        memset(vis,0,sizeof(vis));
        ns=n+2*s-n%s;
        for(int i=0;i<ns;++i){
            if(i<n){
                scanf("%d",&a[i]);
                if(++vis[a[i]]>1) ++cnt;
            }
            if(i>=s)
                if(i-s<n&&--vis[a[i-s]]==1) --cnt;
            if(cnt==0) ok[i]=true;
        }
        for(int i=0;i<s;++i){
            bool flag=true;
            for(int j=i;j<ns;j+=s)
                if(!ok[j]){
                    flag=false;
                    break;
                }
            if(flag) ++ans;
        }
        printf("%d\n",ans);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

类似于筛选素数的方法，枚举前缀和即可。

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 <cstdio>
using namespace std;
const int maxn = 1000010;
bool nhp[maxn];
int hp[maxn],hpnum;
int cnt[maxn];
void pre() {
    for(int i = 5; i < 1010; i += 4)
        if(!nhp[i])
            for(int j = i * i; j < maxn; j += i)
                nhp[j] = true;
    for(int i = 5; i < maxn; i+=4)
        if(!nhp[i]) hp[hpnum++] = i;
    for(int i = 0; i < hpnum; ++i)
        for(int j = 0; j < hpnum && hp[i] * hp[j] < maxn; ++j)
            cnt[hp[i]*hp[j]] = 1;
    for(int i = 1; i < maxn; ++i) cnt[i] += cnt[i - 1];
}
int main() {
    pre();
    int n;
    while(~scanf("%d", &n) && n)
        printf("%d %d\n", n, cnt[n]);
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **