2013 腾讯马拉松专题-阿里云开发者社区

第一场

第一题 hdu4500

水题，直接模拟即可

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 25;
int n , m;
int num[maxn][maxn];
int ans[maxn][maxn];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};

bool isDif(int a , int b){
    return a*b < 0;
}

void solve(){
    memset(ans , 0 , sizeof(ans));
    for(int i = 1 ; i <= n ; i++){
       for(int j = 1 ; j <= m ; j++){
          for(int k = 0 ; k < 4 ; k++){
             int x = num[i+dir[k][0]][j+dir[k][1]];
             if(isDif(num[i][j] , x))
                ans[i][j] += abs(x);
             else
                ans[i][j] -= abs(x);
          }
       }
    }
    int x = 1 , y = 1;
    for(int i = 1 ; i <= n ; i++){
       for(int j = 1 ; j <= m ; j++){
          if(ans[i][j] > ans[x][y])
             x = i , y = j;
       }
    }
    printf("%d %d %d\n" , x , y , ans[x][y]);
}

int main(){
    while(scanf("%d%d" , &n , &m) && n+m){
        memset(num , 0 , sizeof(num));
        for(int i = 1 ; i <= n ; i++){
           for(int j = 1; j <= m ; j++)
              scanf("%d" , &num[i][j]);
        }
        solve();
    }
    return 0;
}

第二题 hdu 4501

dp，三维的0/1背包

/*简单的三维0/1背包*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 110;
int n , v1 , v2 , k;
int dp[maxn][maxn][maxn];
struct Good{
    int price;
    int score;
    int val;
};
Good s[maxn];

int solve(){
    int ans = 0;
    memset(dp , 0 , sizeof(dp));//初始化为0因为不要求没有要刚好
    for(int h  = 0 ; h < n ; h++){
       for(int i = v1 ; i >= 0 ; i--){
          for(int j = v2 ; j >= 0 ; j--){
             for(int t = k ; t >= 0 ; t--){
                int tmp = 0; 
                if(i >= s[h].price)         
                   tmp = max(tmp , dp[i-s[h].price][j][t]+s[h].val);
                if(j >= s[h].score)
                   tmp = max(tmp , dp[i][j-s[h].score][t]+s[h].val); 
                if(t >= 1)
                   tmp = max(tmp , dp[i][j][t-1]+s[h].val);
                dp[i][j][t] = max(tmp , dp[i][j][t]); 
                ans = max(ans , dp[i][j][t]);
             } 
          }
       }
    }
    return ans;
}

int main(){
    while(scanf("%d%d%d%d" , &n, &v1, &v2, &k) != EOF){ 
        for(int i = 0 ; i < n ; i++)
           scanf("%d%d%d" , &s[i].price , &s[i].score , &s[i].val);
        printf("%d\n" , solve());
    } 
    return 0;
}

第三题 hdu 4502

dp 区间型的dp问题，定义dp[i]表示时间i之前得到的最大的工资

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 1010;
struct Day{
    int start;
    int end;
    int val;
    bool operator<(const Day &d)const{
        if(start < d.start)
           return true;
        else if(start == d.start && end < d.end)
           return true;
        return false;
    }
};
Day day[maxn];
int m , n;
int dp[maxn];

int solve(){
    int ans = 0;
    memset(dp , 0 , sizeof(dp)); 
    sort(day , day+n);
    for(int i = 0 ; i < n ; i++){
       if(day[i].end <= m)
          dp[day[i].end] = max(dp[day[i].start-1]+day[i].val , dp[day[i].end]); 
       for(int j = day[i].end+1 ; j <= m ; j++)
          dp[j] = max(dp[day[i].end] , dp[j]);
    }
    return dp[m];
}

int main(){
    int Case;
    scanf("%d" , &Case);
    while(Case--){
        scanf("%d%d" , &m , &n);
        for(int i = 0 ; i < n ; i++) 
           scanf("%d%d%d" , &day[i].start , &day[i].end , &day[i].val);
        printf("%d\n" , solve()); 
    }
    return 0;
}

第四题 hdu 4503

思路:根据题目选的3个人互不认识或者都认识则关系相同,从这种关系相同的反面来看就是
3个人只有两个认识，最后一个人不认识,所以可以求这种反面情况的个数,对于第i个人，可以选一个做他的朋友一个即a种情况，剩余一个人选他不认识的人(即非朋友)即n-a-1中情况 (扣除自己是n-a-1)
所以num+=a*(n-a-1),num表示反面情况的总数，但是这里我们应该要注意由于两个人之间的关系是相互的所以我们求出的num实际上是多算了一倍，所以num = num/2

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
   int Case;
   scanf("%d" , &Case);
   while(Case--){
       int n , x;
       scanf("%d" , &n);
       int sum , num;
       num = 0;
       for(int i = 0 ; i < n ; i++){
          scanf("%d" , &x);
          num += x*(n-x-1);    
       }
       sum = n*(n-1)*(n-2)/6;//n个中取出3个的总数
       num /= 2;
       num = sum-num;
       printf("%0.3lf\f" , 1.0*num/sum); 
   }
   return 0;
}

第五题 hdu 4504

简单的dp
dp[i][j]表示的是前i回合得到j分的方案数，那么就有dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + dp[i-1][j-3];
得用__int64才能过

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 100;
int dp[maxn][maxn];
__int64 ans;

int main(){
    int scoreA , scoreB , t;
    while(scanf("%d%d%d" , &scoreA , &scoreB , &t) != EOF){
         t /= 15;
         scoreB += t>>1;
         int dis = scoreB-scoreA;
         int num = (t+1)>>1;
         if(dis <= 0){
           ans = 1;
           for(int i = 1 ; i <= num ; i++)
              ans *= 3;
         }
         else{
           memset(dp , 0 , sizeof(dp));     
           dp[1][1] = dp[1][2] = dp[1][3] = 1;
           for(int i = 2 ; i <= num ; i++){
              for(int j = 1 ; j <= 3*i ; j++){
                 dp[i][j] = dp[i-1][j-1];
                 if(j >= 2)
                   dp[i][j] += dp[i-1][j-2];
                 if(j >= 3)
                   dp[i][j] += dp[i-1][j-3];
              }
           }
           ans = 0;
           for(int i = dis+1 ; i <= num*3 ; i++)
               ans += dp[num][i];
         } 
         printf("%I64d\n" , ans); 
    }
    return 0;
}

第二场

第一题 hdu 4505

水题，直接排序后模拟即可

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 110;
int num[maxn];
int n;

int solve(){
    int ans = 0;
    sort(num , num+n);
    for(int i = 0 ; i < n ; i++){
       if(i == 0)
          ans += num[i]*6+6;
       else{
          if(num[i] == num[i-1])
             ans++;
          else
             ans += (num[i]-num[i-1])*6+6;
       }
    }
    ans += num[n-1]*4;
    return ans;
}

int main(){
    int Case;
    scanf("%d" , &Case);
    while(Case--){
       scanf("%d" , &n);
       for(int i = 0 ; i < n ; i++)
          scanf("%d" , &num[i]);
       printf("%d\n" , solve());
    }
    return 0;
}

第二题 hdu 4506

循环问题，画出图即可知道，然后对k^t利用快速幂来求即可

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
const int mod = 1000000007;
const int maxn = 10010;
int num[maxn];

ll quickPow(ll k , ll t){
    ll ans = 1;
    while(t){
       if(t&1)
         ans = (ans*k)%mod;
       t = t>>1;
       k = (k*k)%mod;
    }
    return ans%mod;
}

void solve(ll n , ll t , ll k){
    k = quickPow(k , t);
    t %= n;
    int tmpMod = n-t;
    for(int i = 0 ; i < n ; i++){
       if(i == 0) 
         printf("%lld" , num[(i+tmpMod)%n]*k%mod);
       else 
         printf(" %lld" , num[(i+tmpMod)%n]*k%mod);
    }
    printf("\n");
}

int main(){
    int Case;
    int n , t , k;
    scanf("%d" , &Case);
    while(Case--){
       scanf("%d%d%d" , &n , &t , &k);
       for(int i = 0 ; i < n ; i++)
          scanf("%d" , &num[i]);
       solve((ll)n , (ll)t , (ll)k);
    }
    return 0;
}

第三题 hdu 4507

第四题 hdu 4508

简单的完全背包问题

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 100010;
int n , m;
int w[maxn] , val[maxn];
int dp[maxn];

int solve(){
    memset(dp , 0 , sizeof(dp));
    for(int i = 0 ; i < n ; i++){
       for(int j = w[i] ; j <= m ; j++) 
          dp[j] = max(dp[j] , dp[j-w[i]]+val[i]);
    }
    return dp[m];
}

int main(){
    while(scanf("%d" , &n) != EOF){
        for(int i = 0 ; i < n ; i++) 
           scanf("%d%d" , &val[i], &w[i]);
        scanf("%d" , &m);
        printf("%d\n" , solve()); 
    } 
    return 0;
}

第五题 hdu 4509

类似最小覆盖问题

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 500010;

struct Seg{
    int left;
    int right;
    bool operator<(const Seg& s1)const{
        if(left < s1.left)
         return true;
        else if(left == s1.left && right > s1.right)
         return true;
        return false;
    }
};
Seg s[maxn];
int n;

int solve(){
    sort(s , s+n);
    int  ans = s[0].right-s[0].left;
    int pre = s[0].right;
    for(int i = 1 ; i < n ; i++){
       if(s[i].left <= pre){
          if(s[i].right > pre){
             ans += s[i].right-pre;
             pre = s[i].right;
          }
       }
       else{
          ans += s[i].right-s[i].left;
          pre = s[i].right;
       }
    }
    return 24*60-ans;
}

int main(){
    char ch[100];
    int x , y;
    while(scanf("%d" , &n) != EOF){
        for(int i = 0 ; i < n ; i++){
           scanf("%s" , ch);
           sscanf(ch , "%d:%d" , &x , &y);
           s[i].left = x*60+y;
           scanf("%s" , ch); 
           sscanf(ch , "%d:%d" , &x , &y);
           s[i].right = x*60+y;
        }
        printf("%d\n" , solve());
    }
    return 0;
}

第三场

第一题 hdu 4510

水题，时间是12小时制

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 100;
int H , M , S;
int h , m , s;

void solve(){
    //秒的处理 
    if(S < s){
       S += 60;
       M--;
       if(M < 0){
         M += 60;
         H--;
       }
    }
    S -= s; 
    //分的处理
    if(M < m){
       M += 60;
       H--;
    }
    M -= m;
    //时的处理
    if(H < h)
      H += 24;
    H -= h;
}

int main(){
    int Case;
    char str[maxn];
    scanf("%d" , &Case);
    while(Case--){
        scanf("%s" , str); 
        sscanf(str , "%d:%d:%d" , &H , &M , &S);
        scanf("%s" , str); 
        sscanf(str , "%d:%d:%d" , &h , &m , &s);
        h %= 24;
        solve(); 
        printf("%02d:%02d:%02d\n" , H%12 , M , S);
    }
    return 0;
}

第二题 hdu 4511

第三题 hdu 4512

很明显题目就是要求两个序列的最长公共上升子序列
我们只要去枚举分割序列的点，然后去求两个序列的最长公共上升子序列。
注意这个地方就是这个分割点属于左边或右边序列的时候求出的最长公共上升子序列的长读是不同的。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 210;
int num[MAXN];
int num1[MAXN] , num2[MAXN];
int n , pos1 , pos2 , maxNum;
int dp[MAXN][MAXN];

int DP(){
    int Max;
    for(int i = 1 ; i <= pos1 ; i++){
       Max = 0; 
       for(int j = 1 ; j <= pos2 ; j++){
          dp[i][j] = dp[i-1][j];
          if(num1[i] > num2[j] && Max < dp[i-1][j])
            Max = dp[i-1][j];
          if(num1[i] == num2[j])
            dp[i][j] = Max+1;
       }
    }
    Max = maxNum = 0;
    for(int i = 1 ; i <= pos2 ; i++){
       if(Max < dp[pos1][i]){
          Max = dp[pos1][i];
          maxNum = num2[i];
       }
    }
    return Max;
}

int solve(){
    int ans = 1;
    for(int i = 1 ; i < n ; i++){
       memcpy(num1 , num , sizeof(num)); 
       memcpy(num2 , num , sizeof(num)); 
       reverse(num2+1 , num2+1+n);
       //分界点属于左边
       pos1 = i;
       pos2 = n-i;
       memset(dp , 0 , sizeof(dp));
       int tmpAns = 2*DP();
       if(maxNum < num[i])
          tmpAns++;
       ans = max(ans , tmpAns);
       //分界点属于右边
       pos1 = i-1;
       pos2 = n-i+1;
       memset(dp , 0 , sizeof(dp));
       tmpAns = 2*DP();
       if(maxNum < num[i])
          tmpAns++;
       ans = max(ans , tmpAns);
    }
    return ans;
}

int main(){
    int Case;
    scanf("%d" , &Case);
    while(Case--){
       scanf("%d" , &n);
       for(int i = 1 ; i <= n ; i++)
           scanf("%d" , &num[i]);
       printf("%d\n" , solve());
    }
    return 0;
}

第四题 hdu 4513

第五题 hdu 4514

1 首先利用并查集判圈
2 如果没有环，那么对每一个连通分量进行两次的bfs，最后求最大值

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAX = 100010;
const int MAXN = 1000010;
int n , m , ans , start;
struct Edge{
    int u;
    int e;
    int val;
};
Edge edge[2*MAXN];
int first[MAX] , next[2*MAXN];
int father[MAX];
bool vis[MAX] , rootVis[MAX];
struct Node{
    int x;
    int dis;
};
queue<Node>q;

void init(){
    for(int i = 1 ; i <= n ; i++)
        father[i] = i;
    memset(first , -1 , sizeof(first));
    memset(next , -1 , sizeof(next));
}

int find(int x){
    if(x != father[x])
       father[x] = find(father[x]);
    return father[x];
}

void addEdge(int i){
    edge[i+m].u = edge[i].e;
    edge[i+m].e = edge[i].u;
    edge[i+m].val = edge[i].val;

    next[i] = first[edge[i].u];
    first[edge[i].u] = i; 
    next[i+m] = first[edge[i+m].u];
    first[edge[i+m].u] = i+m; 
}

void bfs(int x){
    memset(vis , false , sizeof(vis));
    q.push((Node){x , 0});
    vis[x] = true;
    ans = 0;
    while(!q.empty()){
        Node tmp = q.front();
        q.pop();
        if(tmp.dis > ans){
           ans = tmp.dis; 
           start = tmp.x; 
        }
        for(int i = first[tmp.x] ; i != -1 ; i = next[i]){
           int x = edge[i].e;
           if(!vis[x]){
              vis[x] = true;
              q.push((Node){x , tmp.dis+edge[i].val});
           } 
        }
    }
}

int main(){
    while(scanf("%d%d",&n , &m) != EOF){
         init();  
         bool isLoop = false;
         for(int i = 1 ; i <= m ; i++){
            scanf("%d%d%d" , &edge[i].u,&edge[i].e,&edge[i].val);     
            if(isLoop)
               continue;
            int fx = find(edge[i].u);
            int fy = find(edge[i].e);
            if(fx == fy)
               isLoop = true;
            father[fx] = fy;
            addEdge(i);   
         }
         if(isLoop)
             puts("YES");
         else{
             int Max = 0;
             memset(rootVis , false , sizeof(rootVis));
             for(int i = 1 ; i <= n ; i++){
                 if(!rootVis[find(i)]){
                    rootVis[find(i)] = true; 
                    bfs(i);
                    bfs(start);
                    Max = max(Max , ans);
                 }
             }
             printf("%d\n" , Max);
         }
    }
    return 0;
}

第四场

第一题 hdu 4515

直接向上加或向下减，注意月和年已经润年的处理。或者利用java的日期类calendar

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int year , month , day;
int tmpYear , tmpMonth , tmpDay;
int monthArr[] = {31,28,31,30,31,30,31,31,30,31,30,31};

bool isLoop(int num){
    if((num%4 == 0 && num%100 != 0) || num%400 == 0)
       return true;
    return false;
}

void add(){
    day++;
    if(day > monthArr[month-1]){
      month++;
      day = 1;
      if(month > 12){
        year++;
        month = 1;
        if(isLoop(year))
          monthArr[1] = 29; 
        else
          monthArr[1] = 28;
      }
    }
}

void cut(){
    tmpDay--;
    if(tmpDay <= 0){
       tmpMonth--;
       if(tmpMonth <= 0){
          tmpYear--;
          tmpMonth = 12;
          if(isLoop(tmpYear))
            monthArr[1] = 29; 
          else 
            monthArr[1] = 28; 
       } 
       tmpDay = monthArr[tmpMonth-1];
    }
}

int main(){
    int Case;
    int d;
    scanf("%d" , &Case);
    while(Case--){
        scanf("%d" , &d); 
        year = tmpYear = 2013;
        month = tmpMonth = 3;
        day = tmpDay = 24;
        int cnt = d;
        while(cnt--)
            add();
        cnt = d;
        monthArr[1] = 28;//这个地方应该要把第二个月改为28
        while(cnt--)
            cut();
        printf("%04d/%02d/%02d " , year,month,day);
        printf("%04d/%02d/%02d\n" , tmpYear,tmpMonth,tmpDay);
    }
    return 0;
}

//日期类月份是从0-11开始的
import java.util.Calendar;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
         int Case , d;
         Scanner cin = new Scanner(System.in);
         Case = cin.nextInt();
         Calendar calendar = Calendar.getInstance();
         while(Case > 0){
             Case--;
             d = cin.nextInt();
             //往上计算
             calendar.set(2013, 2, 24);
             calendar.add(Calendar.DAY_OF_MONTH , d);
             int year = calendar.get(Calendar.YEAR);
             int month = calendar.get(Calendar.MONTH);
             int day = calendar.get(Calendar.DAY_OF_MONTH);
             System.out.printf("%04d/%02d/%02d", year , month+1 , day);
             //往下计算
             calendar.set(2013, 2, 24);
             calendar.add(Calendar.DAY_OF_MONTH , -d);
             year = calendar.get(Calendar.YEAR);
             month = calendar.get(Calendar.MONTH);
             day = calendar.get(Calendar.DAY_OF_MONTH);
             System.out.printf(" %04d/%02d/%02d", year , month+1 , day);
             System.out.println("");
         }
    }

第二题 hdu 4516

第三题 hdu 4517

矩阵覆盖问题

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 2010;
char maze[maxn][maxn];
int mat[maxn][maxn];
int m , n , x , y;

bool isOk(int i , int j , int tmpx , int tmpy){
    if(tmpx <= n && tmpy <= m)
       return mat[tmpx][tmpy]-mat[tmpx][j-1]-mat[i-1][tmpy]+mat[i-1][j-1] == x*y; 
    return false;
}

int solve(){
    int ans = 0; 
    for(int i = 1 ; i <= n ; i++){
       for(int j = 1 ; j <= m ; j++){
          if(maze[i][j] == '*'){
            int tmpx , tmpy;
            //方向1
            tmpx = i+x-1;
            tmpy = j+y-1;
            if(isOk(i , j , tmpx , tmpy)) 
               ans++;
            //方向2
            if(x == y) 
               continue;
            tmpx = i+y-1;
            tmpy = j+x-1;
            if(isOk(i , j , tmpx , tmpy)) 
               ans++;
          }
       }
    }
    return ans;
}

int main(){
    while(scanf("%d%d" , &n , &m) && n+m){
        scanf("%d%d%*c" , &x , &y);
        memset(mat , 0 , sizeof(mat));
        for(int i = 1 ; i <= n ; i++){
           for(int j = 1 ; j <= m ; j++){ 
              maze[i][j] = getchar();
              mat[i][j] += mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1];
              if(maze[i][j] == '*')
                 mat[i][j]++;
           }
           getchar();
        }
        printf("%d\n" , solve());
    }
    return 0;
}

第四题 hdu 4518

第五题 hdu 4519

水题

#include<stdio.h>

int main(){
    int n , k , m;
    int Case , ans;
    scanf("%d" , &Case);
    while(Case--){
        scanf("%d%d%d" , &n , &k , &m); 
        if(m > n)
          ans = k;
        else
          ans = (n*k)%m == 0 ? (n*k)/m : (n*k)/m+1;
        printf("%d\n" , ans);
    }
    return 0;
}

第五场

第一题 hdu4520

水题

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 25;
double score[maxn];
int n;

int solve(){
    int maxScore , minScore;
    double avrScore = 0.0;
    //求出最大和最小的分数
    maxScore = minScore = 1; 
    for(int i = 1 ; i <= n ; i++){
       if(score[i] >= score[maxScore]) 
          maxScore = i;
       if(score[i] <= score[minScore])
          minScore = i; 
    }
    score[maxScore] = -1;
    score[minScore] = -1;
    //求平均分
    for(int i = 1 ; i <= n ; i++)
       if(score[i] != -1) 
         avrScore += score[i];
    avrScore /= (n-2);
    int ans = 1;
    for(int i = 1 ; i <= n ; i++){
       if(score[i] != -1){
         if(fabs(score[i]-avrScore) < fabs(avrScore-score[ans])) 
            ans = i; 
       }
    }
    return ans;
}

int main(){
    while(scanf("%d" , &n) && n){
        for(int i = 1 ; i <= n ; i++) 
           scanf("%lf" , &score[i]);
        printf("%d\n" , solve());
    }
    return 0;
}

第二题 hdu4521

第三题 hdu4522

最短路问题
1 mazeOne表示只有硬座， mazeTwo表示卧铺
2 然后我们做两次的dij,然后比较求出最小值即可。注意要使用long long（我也不懂为什么，因为这wa了一次）
3 注意边是单向的

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int INF = 1<<30;
const int maxn = 210;
int mazeOne[maxn][maxn] , mazeTwo[maxn][maxn];
int n , t , D1 , D2;
int start , end;
long long dis[maxn];

void Dij(int G[maxn][maxn]){ 
    bool vis[maxn];
    memset(vis , false , sizeof(vis));
    for(int i = 1 ; i <= n ; i++)
       dis[i] = INF;
    dis[start] = 0;
    for(int i = 1 ; i <= n ; i++){
       int pos = -1;
       for(int j = 1 ; j <= n ; j++)
          if(!vis[j] && (pos == -1 || dis[j] < dis[pos]))   
             pos = j;
       vis[pos] = true;
       for(int j = 1 ; j <= n ; j++)
          if(!vis[j] && (dis[j] > dis[pos]+G[pos][j])) 
             dis[j] = dis[pos]+G[pos][j]; 
    }
}

long long solve(){
    long long ans = INF;
    //对硬座求最短路
    Dij(mazeOne);
    if(dis[end] != INF)
       ans = min(ans , D1*dis[end]);
    //对卧铺求最短路
    Dij(mazeTwo);
    if(dis[end] != INF)
       ans = min(ans , D2*dis[end]);
    return ans == INF ? -1 : ans;
}

void init(){
    for(int i = 1 ; i <= n ; i++){
       for(int j = 1 ; j <= n ; j++){    
          mazeOne[i][j] = INF;
          mazeTwo[i][j] = INF;
       }
       mazeOne[i][i] = 0;
       mazeTwo[i][i] = 0;
    }
}

int main(){
    int Case , k;
    char str[maxn*maxn];
    scanf("%d" , &Case);
    while(Case--){
        scanf("%d%d" , &n , &t); 
        init(); 
        for(int i = 0 ; i < t ; i++){
           scanf("%s" , str); 
           scanf("%d" , &k); 
           int len = strlen(str);
           int i = 0 , j , x , y;
           while(i < len){
               x = y = 0;
               for(j = i ; j < len && str[j] != '+' ; j++) 
                  x = 10*x + str[j]-'0'; 
               i = j+1;
               for(j++ ; j < len && str[j] != '+' ; j++) 
                  y = 10*y + str[j]-'0'; 
               mazeOne[x][y] = 1;
               if(k)
                 mazeTwo[x][y] = 1;
           }
        }
        scanf("%d%d" , &D1 , &D2);
        scanf("%d%d" , &start , &end);
        printf("%lld\n" , solve());
    }
    return 0;
}

第四题 hdu4523

水题

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

//一个n边形切m刀最多为n+m边形
const int maxn = 110;
char str[maxn];
int numN[maxn] , numM[maxn] , numP[maxn];
int posN , posM , posP;

void getNum(int *num , char *s , int pos){
    int len = pos;
    for(int i = 0 ; i < len ; i++)
       num[--pos] = s[i]-'0';
}

bool isEqual(int *sum){
    for(int i = 0 ; i < posM ; i++)
       if(sum[i] != numM[i])
          return false;
    return true;
}

bool solve(){
    if(posM == 1 && numM[0] < 3)
       return false;
    int sum[maxn];
    memset(sum , 0 , sizeof(sum));
    int len = max(posN , posP);
    for(int i = 0 ; i < len ; i++){
       sum[i] += numN[i]+numP[i];
       sum[i+1] += sum[i]/10;
       sum[i] %= 10;
    }
    int pos = maxn-1;
    while(!sum[pos] && pos >= 0)
        pos--;
    if(posP == 1 && numP[0] == 0)
       return isEqual(sum);
    for(int i = max(pos , posM) ; i >= 0 ; i--){
       if(sum[i] > numM[i]) 
         return true;
       if(sum[i] < numM[i])
         return false;
    }
    return true;
}

int main(){
    while(scanf("%s" , str) != EOF){
       posN = strlen(str);
       memset(numN , 0 , sizeof(numN)); 
       getNum(numN , str , posN); 
       
       scanf("%s" , str);
       posM = strlen(str);
       memset(numM , 0 , sizeof(numM)); 
       getNum(numM , str , posM);
      
       scanf("%s" , str); 
       posP = strlen(str);
       memset(numP , 0 , sizeof(numP)); 
       getNum(numP , str , posP);
      
       printf("%s\n" , solve() ? "YES" : "NO");
    }
    return 0;
}

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		BigInteger n , m , p;
		Scanner cin = new Scanner(System.in);
		while(cin.hasNextBigInteger()){
			n = cin.nextBigInteger();
			m = cin.nextBigInteger();
			p = cin.nextBigInteger();
			BigInteger sum = n.add(p);
			BigInteger tmp = BigInteger.valueOf(0);
			BigInteger tmp1 = BigInteger.valueOf(1);
			BigInteger tmp2 = BigInteger.valueOf(2);
			if(p.equals(tmp)){
				if(sum.equals(m))
					System.out.println("YES");
				else 
					System.out.println("NO");
			}
			else if(m.equals(tmp1) || m.equals(tmp2))
				System.out.println("NO");
			else {
				if(sum.compareTo(m) >= 0)
					System.out.println("YES");
				else 
					System.out.println("NO");
			}
		}
	}
}

第五题 hdu4524

水题

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 1000010;
const char str[2][100] = {"yeah~ I escaped ^_^" , "I will never go out T_T"};
int num[maxn];
int n;

bool isOk(){
    for(int i = 0 ; i < n ; i++){
       if(num[i] > num[i+1])
          return false;
       else if(num[i] == num[i+1])
          i++;
       else
          num[i+1] -= num[i];
    }
    return true;
}

int main(){
    int Case;
    scanf("%d" , &Case);
    while(Case--){
        scanf("%d" , &n); 
        memset(num , -1 , sizeof(num));
        for(int i = 0 ; i < n ; i++)
           scanf("%d" , &num[i]);
        printf("%s\n" , isOk() ? str[0] : str[1]); 
    }
    return 0;
}

第六场

第一题 hdu 4525

注意
1 题目没有说明输入的值都是整数，所以应该要double
2 当开始输入的和sum > k的时候输出0
3 还有当fabs(k1+k2) <= 1的时候只有sum > k时才有可能停止生长

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 10010;
double num[maxn];
double k1 , k2 , k , sum;
int n;

double Pow(double s , int num){
    double sum = 1.0;
    for(int i = 1 ; i <= num ; i++)
       sum *= s;
    return sum;
}

void solve(){
    if(sum > k){
       printf("0\n");
       return;
    }
    double sumk = k1+k2;
    if(fabs(sumk) <= 1)
       printf("inf\n");
    else{
       int i;
       double tmp = 1.0*k/sum;
       for(i = 1 ; i < maxn ; i++)
          if(Pow(sumk , i) > tmp) 
            break;
       printf("%d\n" , i);
    }
}

int main(){
    int Case  = 1 , T;
    scanf("%d" , &T);
    while(T--){
       scanf("%d%lf%lf%lf" , &n , &k1 , &k2 , &k); 
       sum = 0;
       for(int i = 0 ; i < n ; i++){ 
          scanf("%lf" , &num[i]);
          sum += num[i];
       }
       printf("Case #%d: " , Case++);
       solve(); 
    }
    return 0;
}

第二题 hdu 4526

dp问题
1 dp[i][j]表示前i辆车载了j个人的最低价钱
2 那么dp[i][j] = min{dp[i][j] , dp[i-1][j]+(n-j)*(t[i]-t[i-1]) , dp[i-1][j-p]+d+(n-j+p)*(t[i]-t[i+1])}
3 当第i辆车来的时候，我们考虑要坐上这辆车的时候，那么这辆车最多可以载的人数为z[i]，但是这个时候有个问题就是如果i-1辆车之后剩余的人数小于z[i]，那么我们必须去枚举i辆车要载几个人
4 如果k辆车能够载的总人数比n小，那么是impossible的

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 110;
struct Car{
    int t;
    int z;
};
Car car[maxn];
int n , k , d , s;
int dp[maxn][maxn];

int solve(){
    memset(dp , INF , sizeof(dp));
    dp[0][0] = 0;
    for(int i = 1 ; i <= k ; i++){
       for(int j = 0 ; j <= n ; j++){
           dp[i][j] = min(dp[i][j] , dp[i-1][j]+(n-j)*(car[i].t-car[i-1].t));
           for(int p = 1 ; p <= car[i].z ; p++){
              if(j >= p){
                int tmp = dp[i-1][j-p]+d+(n-j+p)*(car[i].t-car[i-1].t);
                dp[i][j] = min(dp[i][j] , tmp); 
              }
           }
       }
    }
    int ans = INF;
    for(int i = 1 ; i <= n ; i++)
        ans = min(ans , dp[i][n]);
    return ans;
}

int main(){
    int Case , sum;
    scanf("%d" , &Case);
    while(Case--){
        scanf("%d%d%d%d" , &n,&k,&d,&s); 
        sum = 0;
        for(int i = 1 ; i <= k ; i++){ 
            scanf("%d%d" , &car[i].t , &car[i].z);
            sum += car[i].z; 
        }
        if(sum < n)
            printf("impossible\n");
        else
            printf("%d\n" , solve());
    }
    return 0;
}

第三题 hdu 4527

一秒一秒的模拟

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

struct Node{
    int x;
    int y;
    int d;
    int t;
};
queue<Node>q;
int mat[8][8];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}}; 

void output(){
    for(int i = 1 ; i <= 6 ; i++){
        printf("%d" , mat[i][1]);
        for(int j = 2 ; j <= 6 ; j++) 
            printf(" %d" , mat[i][j]); 
        printf("\n");
    }
    printf("\n");
}

bool isOk(int x , int y){
    return x >= 1 && x <= 6 && y >= 1 && y <= 6;           
}

void add(int x , int y , int t){
    mat[x][y] = 0;
    for(int i = 0 ; i < 4 ; i++){
        int tmpx = x+dir[i][0];
        int tmpy = y+dir[i][1];
        if(isOk(tmpx , tmpy))   
           q.push((Node){tmpx , tmpy , i , t}); 
    }
}

void bfs(int x , int y){
    add(x , y , 1);
    int t = 1;//当前是第一秒
    while(!q.empty()){
         while(!q.empty()){//把所有同一秒的点全部处理完才进行下一秒
              Node node = q.front();
              if(node.t != t)
                 break;
              q.pop();
              int tmpx = node.x;
              int tmpy = node.y;
              if(mat[tmpx][tmpy])
                 mat[tmpx][tmpy]++;
              else{
                 tmpx += dir[node.d][0];     
                 tmpy += dir[node.d][1];
                 if(isOk(tmpx , tmpy))   
                    q.push((Node){tmpx , tmpy , node.d , node.t+1}); 
              }
         }     
         //搜索下一秒会爆炸的点
         for(int i = 1 ; i <= 6 ; i++){
            for(int j = 1 ; j <= 6 ; j++){
               if(mat[i][j] > 4)   
                  add(i , j , t+1);
            }        
         }
         t++;
    }
}

int main(){
    int m , x , y;
    while(scanf("%d" , &mat[1][1]) != EOF){
        for(int i = 1 ; i <= 6 ; i++){
            for(int j = 1 ; j <= 6 ; j++){
                if(i+j == 2) 
                    continue;
                scanf("%d" , &mat[i][j]);
            } 
        }
        scanf("%d" , &m);
        for(int i = 0 ; i < m ; i++){
            scanf("%d%d" , &x , &y);
            mat[x][y]++; 
            if(mat[x][y] > 4)
                bfs(x , y); 
        }
        output();
    } 
    return 0;
}

第四题 hdu 4528

第五题 hdu 4529

2013 腾讯马拉松专题

热门文章

最新文章

相关课程

相关电子书

相关实验场景