Chengrui's Blog

0%

发表于 分类于 Disqus：

Rank 6。
就出了一道题，还CE了一次。然后剩下的时间就一直不知道在干什么，总是来回换题想，没看出来D题是个DP，当时仔细想想，肯定能出。

B：POJ 3278
简单BFS，一开始没写cstring头文件CE了。23分钟AC。

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>
#include<queue>
using namespace std;
const int maxn=100010;
int n,k,d[maxn*2];
queue<int> q;
int main(){
    while(cin>>n>>k){
        memset(d,-1,sizeof(d));
        while(!q.empty()) q.pop();
        q.push(n);
        d[n]=0;
        while(!q.empty()){
            if(d[k]!=-1) break;
            int cur=q.front();q.pop();
            if(cur&&d[cur-1]==-1) q.push(cur-1),d[cur-1]=d[cur]+1;
            if(cur<2*maxn-1&&d[cur+1]==-1) q.push(cur+1),d[cur+1]=d[cur]+1;
            if(cur*2<200000&&d[cur*2]==-1) q.push(cur*2),d[cur*2]=d[cur]+1;
        }
        cout<<d[k]<<endl;
    }
    return 0;
}

D：POJ 3280
当时没看出来是道DP，赛后补的。
状态转移方程：
d(i,j)=min(d(i+1,j)+min(a[i].add,a[i].del),d(i,j-1)+min(a[j].add,a[j].del))
递推边界：i≥j时，d(i,j)=0
特殊情况：s[i]=s[j]时，d(i,j)=d(i+1,j-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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2010;
const int inf=0x3f3f3f3f;
char s[maxn];
int d[maxn][maxn],a[27];
int dp(int l,int r){
    if(l>=r) return 0;
    int &k=d[l][r];
    if(k!=inf) return k;
    if(s[l]==s[r]) return k=dp(l+1,r-1);
    return k=min(dp(l,r-1)+a[s[r]-'a'],dp(l+1,r)+a[s[l]-'a']);
}
int main(){
    int n,len;
    while(~scanf("%d%d",&n,&len)){
        memset(a,0,sizeof(a));
        memset(d,0x3f,sizeof(d));
        scanf("%s",s);
        for(int i=0;i<n;++i){
            getchar();
            int c=getchar(),t1,t2;
            scanf("%d%d",&t1,&t2);
            a[c-'a']=min(t1,t2);
        }
        printf("%d\n",dp(0,len-1));
    }
    return 0;
}

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

发表于 分类于 Disqus：

Rank 11。
打得不理想，开场23分钟跟了学长1Y了H题之后，再没出题。赛后补了两道能力之内的题。
B：POJ 2431
比赛时，感觉能出，但一直改G题，没时间想，最后也没提交。
用优先队列储存当前能到达的加油站，每次当无法前进时，取油量最多的停留。

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>
#include<queue>
using namespace std;
const int maxn=10010;
struct node{
    int dis,fuel;
    bool operator < (const node &x) const {
        return dis>x.dis;
    }
};
node a[maxn];
priority_queue<int,vector<int>,less<int> > stop;
int main(){
    int n;
    while(~scanf("%d",&n)){
        memset(a,0,sizeof(a));
        while(!stop.empty()) stop.pop();
        for(int i=0;i<n;++i)
            scanf("%d%d",&a[i].dis,&a[i].fuel);
        sort(a,a+n);
        int L,P,cnt=0,pos=0;
        bool flag=true;
        scanf("%d%d",&L,&P);
        while(L>0){
            L-=P;
            if(L<=0) break;
            while(pos<n&&a[pos].dis>=L)
                stop.push(a[pos].fuel),++pos;
            if(stop.empty()){flag=false;break;}
            P=stop.top();
            stop.pop();
            ++cnt;
        }
        printf("%d\n",flag?cnt:-1);
    }
    return 0;
}

G：POJ 2436
有D种病，N头牛，给牛挤奶，所有挤奶的牛的病的总数不能超过K。
病的总数D≤15，所以可以枚举子集之后遍历每头牛，比赛时，思路是对的，但是一直TLE。赛后参考学长代码，发现要进行状态压缩，之前只做过一道要状态压缩的题，这 次完全没想到。还有一个可以优化的地方，在枚举子集时，只需要对当前疾病数等于K的进行统计，因为这样一定是最优解。

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>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
int cow[maxn],a[16];
int solve(const int &n,const int &s){
    int cnt=0;
    for(int i=0;i<n;++i)
        if((s|cow[i])==s) ++cnt;
    return cnt;
}
int main(){
    int N,D,K;
    for(int i=0;i<16;++i) a[i]=1<<i;
    while(~scanf("%d%d%d",&N,&D,&K)){
        memset(cow,0,sizeof(cow));
        for(int i=0;i<N;++i){
            int k,id;
            scanf("%d",&k);
            while(k--){
                scanf("%d",&id);
                cow[i]|=a[id-1];
            }
        }
        int ans=0,s=1<<D;
        for(int i=0;i<s;++i){
            int cnt=0;
            for(int j=0;j<D;++j)
                if(i&a[j]) ++cnt;
            if(cnt==K) ans=max(ans,solve(N,i));
        }
        printf("%d\n",ans);
    }
    return 0;
}

H：POJ 2437
给出木板长度、沼泽个数和每个沼泽的左右端点，沼泽互补相交，求使用木板的最少个数。简单贪心，对区间排序之后，遍历每个区间铺就好了。比赛时提交的代码，求铺当前区 间个数，用了个无脑循环，600+ms，险些超时，赛后修改后提交47ms。以后这种问题要注意。

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<cstdio>
#include<algorithm>
using namespace std;
const int maxn=10010;
struct mud{
    int l,r;
    bool operator < (const mud &x) const {
        return l<x.l;
    }
}a[maxn];
int main(){
    int n,l;
    while(~scanf("%d%d",&n,&l)){
        for(int i=0;i<n;++i) scanf("%d%d",&a[i].l,&a[i].r);
        sort(a,a+n);
        int pos=0,cur=0,cnt=0;
        while(pos<a[n-1].r){
            if(pos<a[cur].l) pos=a[cur].l;
            //原本这写的while(pos<a[cur].r) pos+=l,++cnt; 差点超时。
            if(pos<a[cur].r){
                int t=a[cur].r-pos,num=t/l;
                if(t%l) ++num;
                pos+=l*num,cnt+=num;
            }
            ++cur;
        }
        printf("%d\n",cnt);
    }
    return 0;
}

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

发表于 分类于 Disqus：

给出多个序列，求每个序列的最长上升子序列（LIS：Longest Increasing Subsequence）。
紫书上只给出了LIS的O(n^2)算法，百度O(nlogn)算法，顺便出了这道。遍历数组，用数组储存每个上升子序列的最小结尾。对当前数二分查找求下界，替换原 结尾。

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
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=40010;
int a[maxn],ans[maxn],len;
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;++i) cin>>a[i];
        ans[1]=a[1];
        len=1;
        for(int i=2;i<=n;++i)
            if(a[i]>ans[len]) ans[++len]=a[i];
            else{
                int pos=lower_bound(ans,ans+len,a[i])-ans;
                ans[pos]=a[i];
            }
        cout<<len<<endl;
    }
    return 0;
}

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

发表于 分类于 Disqus：

Rank 5，AC5道，全部1Y。
开场读错了A题，打了就交，直接WA。后来一路跟题，出了几个水题。刷完水题之后，卡在一道BFS上，浪费了不少时间，导致两道简单DP出得特别晚。后来卡D题的BF S，没有想到进行预处理，也一直没有AC。
C：POJ 3668
出了H之后，继续跟榜，25分钟1Y。
给出n个点，求有多少个不平行的直线。枚举每两个点的连线，用set储存斜率，判断是否有斜率不存在的情况后，求和输出。

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<set>
using namespace std;
const int maxn=200;
struct point{
    int x,y;
    point(int x=0,int y=0):x(x),y(y){}
}a[maxn];
set<double> k;
int main(){
    int n;
    while(cin>>n){
        k.clear();
        bool flag=false;
        for(int i=0;i<n;++i)
            cin>>a[i].x>>a[i].y;
        for(int i=0;i<n;++i)
            for(int j=i+1;j<n;++j)
                if(a[i].x==a[j].x) flag=true;
                else k.insert((double)(a[i].y-a[j].y)/(a[i].x-a[j].x));
        cout<<k.size()+flag<<endl;
    }
    return 0;
}

D：POJ 3669
m颗流星，每颗毁坏目标点和目标点周围四个点，给出流星的落点和时间，求从原点走到安全地方的最短时间。首先进行预处理，记录每个点被毁坏的时间，然后BFS求解。
比赛时没有想到预处理的方式，WA好几次最后也没出，赛后补的这道题。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> pii;
const int maxn=310;
const int inf=0x3f3f3f3f;
const int go[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int m,g[maxn][maxn],vis[maxn][maxn];
queue<pii> q;
void boom(int x,int y,int t){
    g[x][y]=min(g[x][y],t);
    for(int i=0;i<4;++i){
        int a=x+go[i][0],b=y+go[i][1];
        if(a>=0&&a<maxn&&b>=0&&b<maxn)
            g[a][b]=min(g[a][b],t);
    }
    return;
}
int main(){
    while(~scanf("%d",&m)){
        while(!q.empty()) q.pop();
        memset(g,0x3f,sizeof(g));
        memset(vis,-1,sizeof(vis));
        for(int i=0;i<m;++i){
            int x,y,t;
            scanf("%d%d%d",&x,&y,&t);
            boom(x,y,t);
        }
        pii tmp=make_pair(0,0);
        q.push(tmp);
        vis[0][0]=0;
        while(!q.empty()){
            tmp=q.front();
            q.pop();
            if(g[tmp.first][tmp.second]==inf) break;
            for(int i=0;i<4;++i){
                int a=tmp.first+go[i][0],b=tmp.second+go[i][1];
                if(vis[a][b]!=-1||g[a][b]<=vis[tmp.first][tmp.second]+1) continue;
                if(a>=0&&a<maxn&&b>=0&&b<maxn){
                    vis[a][b]=vis[tmp.first][tmp.second]+1;
                    q.push(make_pair(a,b));
                }
            }
        }
        if(g[tmp.first][tmp.second]==inf) printf("%d\n",vis[tmp.first][tmp.second]);
        else printf("-1\n");
    }
    return 0;
}

E：POJ 3670
跟F题很像的一道题，把F的代码粘贴两次，之后修改下就过了，145分钟1Y。

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
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=30010;
int a[maxn];
int main(){
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n){
        int ans=0,ans1=maxn,ans2=maxn,one=0,n_one=0,two=0,three=0;
        for(int i=0;i<n;++i){
            cin>>a[i];
            if(a[i]==1) ++one;
            //else ++n_one;
        }
        int pos=0;
        for(int i=0;i<n;++i){
            if(a[i]==1) --one;
            if(ans1>one+n_one) pos=i;
            ans1=min(one+n_one,ans1);
            if(a[i]!=1) ++n_one;
        }
        for(int i=pos;i<n;++i)
            if(a[i]==2) ++two;
        for(int i=pos;i<n;++i){
            if(a[i]==2) --two;
            ans2=min(two+three,ans2);
            if(a[i]==3) ++three;
        }
        ans=ans1+ans2;
        ans1=maxn,ans2=maxn,one=0,n_one=0,two=0,three=0;
        for(int i=0;i<n/2;++i)
            swap(a[i],a[n-1-i]);
        for(int i=0;i<n;++i)
            if(a[i]==1) ++one;
            //else ++n_one;
        pos=0;
        for(int i=0;i<n;++i){
            if(a[i]==1) --one;
            if(ans1>one+n_one) pos=i;
            ans1=min(one+n_one,ans1);
            if(a[i]!=1) ++n_one;
        }
        for(int i=pos;i<n;++i)
            if(a[i]==2) ++two;
        for(int i=pos;i<n;++i){
            if(a[i]==2) --two;
            ans2=min(two+three,ans2);
            if(a[i]==3) ++three;
        }
        cout<<min(ans1+ans2,ans)<<endl;
    }
    return 0;
}

F：POJ 3671
D题卡了好久，一直WA，在119分钟最后一次D题提交WA之后，去做这道，130分钟1Y。
给出一个有1、2组成的序列，求最少改动几个数字使得前面是1，后面是2。
简单DP，没写状态转移方程，直接遍历求每个位置改动的最小值输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=30010;
int a[maxn];
int main(){
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n){
        int ans=maxn,one=0,two=0;
        for(int i=0;i<n;++i){
            cin>>a[i];
            if(a[i]==1) ++one;
        }
        for(int i=0;i<n;++i){
            if(a[i]==1) --one;
            ans=min(one+two,ans);
            if(a[i]==2) ++two;
        }
        cout<<ans<<endl;
    }
    return 0;
}

G：POJ 3672
AC了C题之后，看到有出这个的，又跟了。30分钟1Y。
输入u、f、d表示上坡、平地、下坡，求给定时间的最长路程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<string>
#include<algorithm>
#include<iostream>
#include<set>
using namespace std;
const int maxn=200;
int main(){
    int m,t,u,f,d;
    while(cin>>m){
        int cnt=0;
        cin>>t>>u>>f>>d;
        for(int i=0;i<t;++i){
            cin.get();
            if(cin.get()=='f') m-=2*f;
            else m-=(u+d);
            if(m<0) break;
            ++cnt;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

H：POJ 3673
简单求和，A题WA之后，看榜上有人AC之后马上跟的，12分钟1Y。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
int main(){
    string s1,s2;
    while(cin>>s1>>s2){
        long long sum=0;
        for(int i=0;i<s1.size();++i)
            for(int j=0;j<s2.size();++j)
                sum+=(s1[i]-'0')*(s2[j]-'0');
        cout<<sum<<endl;
    }
    return 0;
}

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

发表于 分类于 Disqus：

Rank 6，一共AC了6题，其中5道1Y。
感觉这场比赛打得还可以，能出的题都出了，就是一开始选题出现了问题，先去做了DP，导致很多水题出的晚了，时间上占了劣势，好在前5道题AC的题都是1Y，没有很多 罚时。AC6题之后，看其他题都没什么思路，与学长们在知识储量上的劣势马上表现出来了，学长们继续打代码、出题，我只剩翻书、刷榜了，一直到结束。
A：POJ 2385
接苹果的题，是个DP。思路比较好想，27分钟1Y。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
int a[maxn];
int d[maxn][35][2];
int main(){
    int t,w;
    while(~scanf("%d%d",&t,&w)){
        memset(d,0,sizeof(d));
        memset(a,0,sizeof(a));
        int ans=0;
        for(int i=0;i<t;++i) scanf("%d",&a[i]),--a[i];
        for(int i=t-1;i>=0;--i){
            for(int j=0;j<=w;++j){
                if(j){
                    d[i][j][0]=max(d[i+1][j-1][1]+(a[i]==1),d[i+1][j][0]+(a[i]==0));
                    d[i][j][1]=max(d[i+1][j-1][0]+(a[i]==0),d[i+1][j][1]+(a[i]==1));
                }
                else d[i][j][0]=d[i+1][j][0]+(a[i]==0),d[i][j][1]=d[i+1][j][1]+(a[i]==1);
            }
        }
        for(int i=0;i<=w;++i)
            ans=max(ans,d[0][i][0]);
        printf("%d\n",ans);
    }
    return 0;
}

B：POJ 2386
出了A题之后，看别人都A了好几道别的题了，就马上去做这道。
DFS判连通的题，模板题。44分钟1Y。

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
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=110;
const int go[8][2]={{-1,-1},{0,-1},{1,-1},{-1,0},{1,0},{-1,1},{0,1},{1,1}};
char g[maxn][maxn];
int m,n,a[maxn][maxn];
bool vis[maxn][maxn];
void dfs(int u,int v,int cnt){
    if(u<1||u>n||v<1||v>m) return;
    for(int i=0;i<8;++i){
        int a=u+go[i][0],b=v+go[i][1];
        if(!vis[a][b]&&g[a][b]=='W'){
            vis[a][b]=true;
            dfs(a,b,cnt);
        }
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n>>m){
        memset(a,0,sizeof(a));
        memset(g,0,sizeof(g));
        memset(vis,0,sizeof(vis));
        int cnt=0;
        for(int i=1;i<=n;++i){
            cin.get();
            for(int j=1;j<=m;++j)
                g[i][j]=cin.get();
        }
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                if(!vis[i][j]&&g[i][j]=='W'){
                    vis[i][j]=true;
                    dfs(i,j,++cnt);
                }
        cout<<cnt<<endl;
    }
    return 0;
}

C：POJ 2387
清完水题开始做的，最小生成树的题，模板题，一开始忽略了，同结点之间可能有多条路径WA了2次。97分钟AC。

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<algorithm>
#include<cstring>
using namespace std;
const int maxn=1010;
const long long inf=0x3f3f3f3f;
long long w[maxn][maxn],v[maxn];
long long d[maxn];
int main(){
    int t,n;
    while(cin>>t>>n){
        memset(v,0,sizeof(v));
        memset(w,0x3f,sizeof(w));
        for(int i=0;i<t;++i){
            long long u,v,len;
            cin>>u>>v>>len;
            u=n-u,v=n-v;
            w[u][v]=w[v][u]=min(len,w[u][v]);
        }
        for(int i=0;i<n;++i) d[i]=(i==0?0:inf);
        for(int i=0;i<n;++i){
            long long x,m=inf;
            for(int y=0;y<n;++y) if(!v[y]&&d[y]<=m) m=d[x=y];
            v[x]=1;
            for(int y=0;y<n;++y) d[y]=min(d[y],d[x]+w[x][y]);
        }
        cout<<d[n-1]<<endl;
    }
    return 0;
}

D：POJ 2388
水题。求小于等于当前数的数的个数。48分钟1Y。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10010;
int a[maxn];
int main(){
    int n;
    while(cin>>n){
        for(int i=0;i<n;++i) cin>>a[i];
        sort(a,a+n);
        cout<<a[n/2]<<endl;
    }
    return 0;
}

E：POJ 2389
大数相乘，套模板。57分钟1Y。

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
58
59
60
61
62
63
64
65
66
67
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
struct Big{
    int len;
    long long data[1001];
    void clear(){
        memset(this,0,sizeof(*this));
    }
    long long & operator [](int k){
        return data[k];
    }
    Big operator * (Big A){
        Big temp;
        temp.clear();
        temp[0]=data[0]*A[0];
        temp.len=len+A.len-1;
        for(int i=1;i<=len;i++)
            for(int j=1;j<=A.len;j++){
                temp[i+j-1]+=A[j]*data[i];
                temp[i+j]+=temp[i+j-1]/10000;
                temp[i+j-1]%=10000;
            }
        while(temp[temp.len+1]) ++temp.len;
        while(!temp[temp.len]) --temp.len;
        if(!temp.len) temp.len=1;
        return temp;
    }
};
istream& operator >> (istream &in,Big& b){
    b.clear();
    string s,s0;
    if(!(in>>s)) return in;
    b[0]=s[0]=='-'?-1:1;
    if(s[0]=='-'||s[0]=='+') s0=s.substr(1);
    else s0=s;
    b.len=((int)s0.size()+3)/4;
    int k=(int)s0.size()%4;
    if(!k) k=4;
    for(int i=0;i<k;i++){
        b[b.len]*=10;
        b[b.len]+=s0[i]-'0';
    }
    for(int i=b.len-1;i>0;i--)
        b[b.len-i]=1000*(s0[4*(i-1)+k]-'0')+100*(s0[4*(i-1)+k+1]-'0')+10*(s0[4*(i-1)+k+2]-'0')+s0[4*(i-1)+k+3]-'0';
    if(b.len==1&&!b[1]) b[0]=1;
    return in;
}
ostream& operator << (ostream &out,Big& b){
    if(b[0]==-1) printf("-");
    printf("%lld",b[b.len]);
    for(int i=b.len-1;i>=1;i--)
        printf("%04lld",b[i]);
    return out;
}
int main(){
    Big a,b,c;
    while(cin>>a>>b){
        c=a*b;
        cout<<c<<endl;
    }
    return 0;
}

F：POJ 2390
水题，算利率。51分钟1Y。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=10010;
int a[maxn];
int main(){
    double a,b,c;
    while(cin>>a>>b>>c){
        a/=100.0;
        a+=1;
        a=pow(a,c);
        cout<<(int)(a*b)<<endl;
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出n*m个格子，每个格子里有一个机器人，可以执行东南西北四种指令，但是移动出格就会爆炸。给出四种指令的个数，求最多完成多少次指令。
首先对输入数据进行处理，使得cw≥ce、cn≥cs且先执行东西方向的来回移动比先执行南北方向来回移动更佳。然后执行东西移动，再用类似于UVa-1610 Party Game的排序方法，对比每次向西移动还是开始南北移动更好。当仅剩西和北两个方向后，模拟至结束。每个样例的复杂度为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
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
int main(){
    LL n,m,t=0;
    while(cin>>n>>m,m||n){
        LL cn,cs,cw,ce,ans=0;
        cin>>cn>>cs>>cw>>ce;
        if(cn<cs) swap(cs,cn);
        if(cw<ce) swap(ce,cw);
        LL t1=n+(m-1)*n*ce*2+(m-1)+(m-1)*(n-1)*cs*2,t2=m+m*(n-1)*cs*2+(n-1)+(m-1)*(n-1)*ce*2;//判断是否需要交换。
        if(cw-ce) t1+=(m-1)*n,t2+=(m-1)*(n-1);
        if(cn-cs) t1+=(m-1)*(n-1),t2+=m*(n-1);
        if(t1<t2) swap(m,n),swap(cn,cw),swap(cs,ce);
        bool flag=true;
        if(ce) ans+=n+(m-1)*n*ce*2,cw-=ce,ce=0,--m,flag=false;
        if(cw){
            ans+=m*n,--cw;
            if(flag) --m;
        }
        cw=min(m,cw);
        while(cw||cn){
            if(cs){//判断是否开始进行南北移动。
                LL t1=m*n+(n-1)*m*2*cs,t2=m*n+(m-1)*n+(m-1)*(n-1)*(2*cs-1);
                if(cn-cs) t1=m*n+(n-1)*m*(2*cs+1),t2=m*n+(m-1)*n+(m-1)*(n-1)*2*cs;
                if(t1>t2||!cw){//cw为0时也要执行南北移动。
                    ans+=m+m*(n-1)*cs*2,cn-=cs,cs=0,--n;
                    if(cn) ans+=m*n,--cn;
                    cn=min(n,cn);
                }
                else ans+=m*n,--m,--cw;
            }
            else if(!cw) ans+=m*cn*(2*n-cn+1)/2,cn=0;
            else if(!cn) ans+=n*cw*(2*m-cw+1)/2,cw=0;
            else{
                ans+=m*n;
                if(m>n) --m,--cw;
                else --n,--cn;
            }
        }
        cout<<"Case "<<++t<<": "<<ans<<endl;
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出n个点和一个值D，在x轴选出最少的点使得对于每个给出点都有一个选出的点离它的欧几里德距离不超过D。
将给出的点转化成区间，就变成了简单的区间选点问题。

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<cmath>
#include<vector>
#include<algorithm>
using namespace std;
double L,D;
struct node{
    double l,r;
    node(const double &x,const double &y){
        double R=sqrt(D*D-y*y);
        this->l=max(x-R,0.0),this->r=min(x+R,L);
        return;
    }
    bool operator < (const node &x) const {
        return r==x.r?l>x.l:r<x.r;
    }
};
vector<node> vil;
int main(){
    while(~scanf("%lf%lf",&L,&D)){
        vil.clear();
        int n,cnt=1;
        scanf("%d",&n);
        for(int i=0;i<n;++i){
            double x,y;
            scanf("%lf%lf",&x,&y);
            vil.push_back(node(x,y));
        }
        sort(vil.begin(),vil.end());
        double pos=vil[0].r;
        for(int i=0;i<(int)vil.size();++i){
            if(pos<=vil[i].r&&pos>=vil[i].l) continue;
            pos=vil[i].r,++cnt;
        }
        printf("%d\n",cnt);
    }
    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
46
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
const int maxn=1000010;
int n,m,pos,ans[maxn],full[maxn];
set<int> d;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        bool flag=true;
        pos=0;
        d.clear();
        memset(ans,0,sizeof(ans));
        memset(full,0,sizeof(full));
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;++i){
            int k;
            scanf("%d",&k);
            if(!flag) continue;
            if(!k) d.insert(i);
            else{
                ans[i]=-1;
                set<int>::iterator it=d.lower_bound(full[k]);
                if(it==d.end()) flag=false;
                else{
                    ans[*it]=k;
                    full[k]=i;
                    d.erase(*it);
                }
            }
        }
        if(!flag) printf("NO\n");
        else{
            bool first=true;
            printf("YES");
            for(int i=0;i<m;++i)
                if(ans[i]>=0)
                    printf("%c%d",first?(first=false,'\n'):' ',ans[i]);
            printf("\n");
        }
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

按照横坐标递增的顺序给出1≤n≤1000个点的坐标，求从左边走到右边再走回来，除了两端的点每个点恰好经过一次的走法的距离和。
书上给出了详细的思路，把问题抽象成两个人从一端走到另一端最短距离和。
状态转移方程为： ** d(i,j)=min(d(i+1,i)+dist(i+1,j),d(i+1,j)+dist(i+1,i)) **
边界为： ** d(n-1,j)=d(n,i)+d(n,j) **
最后dist(2,1)+d(2,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
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
struct point{
    int x,y;
    inline double dist(point a){
        return sqrt((a.x-x)*(a.x-x)+(a.y-y)*(a.y-y));
    }
}a[maxn];
double dist[maxn][maxn],d[maxn][maxn];
int main(){
    int n;
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;++i){
            scanf("%d%d",&a[i].x,&a[i].y);
            for(int j=1;j<i;++j)
                dist[i][j]=a[i].dist(a[j]);
        }
        for(int i=n-1;i>=2;--i){
            for(int j=1;j<i;++j){
                if(i==n-1) d[i][j]=dist[n][i]+dist[n][j];
                else d[i][j]=min(d[i+1][i]+dist[i+1][j],d[i+1][j]+dist[i+1][i]);
            }
        }
        printf("%.2lf\n",dist[2][1]+d[2][1]);
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出mn棋盘上的目标点，求最少用几个皇后可以守卫所有目标点。
类似八皇后做法，2维数组标记行、列、主对角线、副对角线。
有个加速的技巧，测试之后发现1010的棋盘全部守卫至少需要5个，所以上限就是5，当maxd等于5时直接输出，不进行搜索。

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>
using namespace std;
const int maxn=11;
int n,m,t,maxd;
bool g[maxn][maxn],vis[4][maxn*2];
bool guard(){
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            if(g[i][j]&&!vis[0][i]&&!vis[1][j]&&!vis[2][i+j]&&!vis[3][i-j+maxn]) return false;
    return true;
}
bool dfs(int i,int j,int d){
    if(d==maxd){
        if(guard()) return true;
        return false;
    }
    while(i<n){
        while(j<m){
            bool tmp1=vis[0][i],tmp2=vis[1][j],tmp3=vis[2][i+j],tmp4=vis[3][i-j+maxn];
            vis[0][i]=vis[1][j]=vis[2][i+j]=vis[3][i-j+maxn]=true;
            if(dfs(i,j+1,d+1)) return true;
            vis[0][i]=tmp1,vis[1][j]=tmp2,vis[2][i+j]=tmp3,vis[3][i-j+maxn]=tmp4;
            ++j;
        }
        j%=m,++i;
    }
    return false;
}
int main(){
    while(scanf("%d",&n),n){
        scanf("%d",&m);
        memset(g,0,sizeof(g));
        for(int i=0;i<n;++i){
            getchar();
            for(int j=0;j<m;++j)
                if(getchar()=='X') g[i][j]=true;
        }
        for(maxd=0;maxd<5;++maxd){
            memset(vis,0,sizeof(vis));
            if(dfs(0,0,0)) break;
        }
        printf("Case %d: %d\n",++t,maxd);
    }
    return 0;
}

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