2014 西安邀请赛 题解

http://acm.hdu.edu.cn/contests/contest_show.php?cid=521

做的杭电的回放，比赛的时候过了4道题，然后1005正在写，写不完了T_T，然后1002的DFS我们没敢敲，其实是有时间的。

A题

求解文本里面多少个doge不区分大小写。直接水,交上去的时候少复制了一行

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <utility>
#include <string>
#include <iostream>
using namespace std;
#define LL long long
string line;
LL ans = 0;
void work()
{
    for (int i = 0; i < line.length(); i ++) {
        if (line[i] >= 'A' && line[i] <= 'Z') line[i] = line[i] - &#39;A&#39; + &#39;a&#39;;
    }
    for (int i = 3; i < line.length(); i ++) {
        if (line[i] == 'e' && line[i-1] == 'g' && line[i-2] == 'o' && line[i-3] == &#39;d&#39;) ans ++;
    }
}
int main()
{
    ans = 0;
    while (cin >> line) {
        work();
    }
    cout << ans << endl;
    return 0;
}

B题

DFS+剪枝就能过，赛后也写了好久才AC的，主要是DFS的时候你得剪枝，剪枝还是很好想的，两个剪枝，一个是当前的时间+remain*edge>deadline必然是不行的，一个当前时间+remain*edge>ans这也是不要继续做的。_主要是dfs的时候你判定一定要写在外面判定好了return完了再进行dfs啊之类的操作，不然会TLE，可能这道题目就是卡你dfs的姿势吧_

#include 
#include 
#include 
#include 
using namespace std;
int n;
int d[44][44];
int dead[44];
bool vis[44];
void floyd(){
    for (int k = 1; k <= n; k ++){
        for (int i = 1; i <= n; i ++){
            for (int j = 1; j <= n; j ++){
                if (d[i][j] > d[i][k] + d[k][j]){
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}
int ans = 1e9;
void dfs(int src, int sumtime,int curtime,int remain){
    if (sumtime >= ans) return;
    if (remain == 0) {
        ans = min(ans,sumtime);
        return;
    }
    //把下面这个for放到里面去判定，就会TLE
    for (int i = 1; i <= n; i ++){
        if (!vis[i] && curtime + d[src][i] > dead[i]){
                return;
        }
    }
    for (int i = 1; i <= n; i ++){
        if (!vis[i] && curtime + d[src][i] > dead[i]){
            return;
        }
        if (!vis[i]){
            if (sumtime + remain * d[src][i] >= ans){
                continue;
            }
            vis[i] = 1;
            //cout << src << ' ' << i << ' ' << sumtime << ' ' << curtime << ' ' << remain << endl;
            dfs(i, sumtime + remain * d[src][i], d[src][i] + curtime, remain - 1);
            vis[i] = 0;
        }
    }
}
int main(int argc, char const *argv[])
{
    while (~scanf("%d", &n)){
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; i ++){
            for (int j = 1; j <= n; j ++){
                scanf("%d", &d[i][j]);
            }
        }
        for (int i = 2; i <= n; i ++){
            scanf("%d", &dead[i]);
        }
        floyd();
        // for (int i = 1; i <= n; i ++){
        //     for (int j = 1; j <= n; j ++){
        //         printf("%d ", d[i][j]);
        //     }cout << endl;
        // }cout << endl;
        ans = 1e9;vis[1] = 1;
        dfs(1,0,0,n-1);
        if (ans == 1e9) printf("-1n");
        else printf("%dn", ans);
    }
    return 0;
}

C题

蘑菇题，题目写的很凌乱，其实就是求一个最短路，一个是z数组得开到1e6才行，一个是需要long long

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define maxn 1111
#define maxx 1000010
ll x[maxx],y[maxx],z[maxx];
int c[maxn][maxn],n,m;
void init(){
    z[0] = (x[0] * 90123 + y[0]) % 8475871 + 1;
    z[1] = (x[1] * 90123 + y[1]) % 8475871 + 1;
    for (int i = 2; i <= n * n; i ++){
        x[i] = (12345 + x[i-1] * 23456 + x[i-2] * 34567 + x[i-1] * x[i-2] * 45678)  % 5837501; 
        y[i] = (56789 + y[i-1] * 67890 + y[i-2] * 78901 + y[i-1] * y[i-2] * 89012)  %  9860381; 
        z[i] = (x[i] * 90123 + y[i]) % 8475871 + 1;
    }
    for (int i = 0; i < n; i ++){
        for (int j = 0; j < n; j ++){
            if (i == j) c[i][j] = 0;
            else c[i][j] = z[i * n + j];
        }
    } 
}
ll dis[maxn];
bool vis[maxn];
ll inf = 1e18;
int spfa(int st) {
    for (int i = 0; i <= n; i++) {
        dis[i] = inf;
        vis[i] = false;
    }
    vis[st] = true;
    dis[st] = 0;
    queue Q;
    Q.push(st);
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        vis[u] = false;
        for (int i = 0; i < n; i ++) {
            if (dis[u] + c[u][i] < dis[i]) {
                dis[i] = dis[u] + c[u][i];
                if (!vis[i]) {
                    vis[i] = true;
                    Q.push(i);
                }
            }
        }
    }
    int ans = 1e9;
    //cout << m << endl;
    for (int i = 1; i < n; i ++){
        dis[i] %= (long long)m;
      //  cout << dis[i] << endl;
        ans = min(ans,(int)(dis[i]));
    }
    return ans;
}
int main(){
    while (~scanf("%d%d", &n, &m)){
        cin >> x[0] >> x[1] >> y[0] >> y[1];
        init();
        cout << spfa(0) << endl;
    }
}

D题

一开始我用dfs做的，竟然栈溢出了，赛后才知道可以改成非递归的dfs。不过队友很给力，随机了几个函数，然后就搞过去了。其实就是爆搜，只是变成for循环了。

#include 
#include 
#include 
#include