首页 > 代码库 > Codeforces Round #257 (Div. 2)

Codeforces Round #257 (Div. 2)

A.Jzzhu and Children

  计算每个人会出现的轮次数,取最后一个且轮次数最大的,注意是用a[i]-1 % m,倒着扫一遍就行了

 

#include <iostream>#include <cstdio>#include <cstdlib>using namespace std;const int maxn = 100+10;int n, m;int a[maxn];int main(){#ifdef LOCAL    freopen("450A.in", "r", stdin);#endif    cin >> n >> m;    int last_one = n, divide = 0;    for(int i = 1; i <= n; i++)         cin >> a[i];    for(int i = n; i >= 1; i--)        if((a[i]-1) / m > divide) {            divide = (a[i]-1)/m;            last_one = i;        }    cout << last_one << endl;    return 0;}

 

B.Jzzhu and Sequences

  很容易推出f[i] = f[i-1]+f[i+1],推出每个六个数一个循环,只需要预处理出f[1]~f[6]就行了

  需要注意的是f[i]可能小于-P,需要(f[i]+2*p)%p,以前写过一种保险的取模,小于0的情况,计算其负数是x倍p,加上(x+1)*P再取模

  例如-5, 2  5/2=2  (-5+3*2)%2 = 1

  

#include <iostream>#include <cstdio>#include <cstdlib>using namespace std;const long long p = 1000000007;long long n, sign, ans;long long f[3];int main(){#ifdef LOCAL    freopen("450B.in", "r", stdin);#endif    cin >> f[0] >> f[1];    f[2] = f[1] - f[0];    cin >> n;    if(((n-1)/3)&1) sign = -1;    else    sign = 1;    ans = sign*f[(n-1)%3];    if(ans > 0) ans %= p;    else    ans = (ans+2*p)%p;    cout << ans << endl;    return 0;}

 

C.Jzzhu and Chocolate

  很烦人的题,首先能够得出最后答案是floor(m/x)*floor(n/y),这个卡了我很久...

  一种方法是直接通过数学分析这个式子

  我是自己乱yy:主要考虑是整除情况:如果m%x0==0那么这个解比起其他x是更优的,

  于是我就分情况写得很细,看代码吧。。。就是如果一边能整除,先让其满足

 

#include <iostream>#include <cstdio>#include <cstdlib>using namespace std;long long n, m, k, ans;int main(){#ifdef LOCAL    freopen("450C.in", "r", stdin);#endif    cin >> n >> m >> k;    if(n+m-2 < k)   cout << -1 << endl;    else {        if(n % (k+1) == 0)            ans = n/(k+1)*m;        else if(m % (k+1) == 0)            ans = m/(k+1)*n;        else if(n - 1 >= k && m - 1 >= k)            ans = max(n/(k+1)*m, m/(k+1)*n);        else if(n - 1 >= k)            ans = n/(k+1)*m;        else if(m - 1 >= k)            ans = m/(k+1)*n;        else {            long long rn = k-(n-1), rm = k-(m-1);            if(m % (rn+1) == 0)                 ans = m/(rn+1);            else if(n % (rm+1) == 0)                ans = n/(rm+1);            else                 ans = max(m/(rn+1), n/(rm+1));        }        cout << ans << endl;    }    return 0;}

 

D.Jzzhu and Cities

  一开始学长讲的 先求一次最短路(不包括铁路) 然后去扫一遍看 哪些铁路能够删去...因为反例很容易举出就是 当两个相连的城市都需要铁路才能到达centre时,是可能只需要一条铁路的,这种方法会跑两条.错在得出的推论是在考虑1-a的铁路时,是不需要考虑a相邻节点的最短路的,因为他们的最短路更新时是w[a,v]+dis[a]...说不清了!这个推论成立的前提是1-a是通路...

  然后我考虑标记每个点是否使用铁路

  在dijkstra做最短路的时候,我们每次都会选边去更新,我把后面铁路也当作普通边加入,不过做上标记,这样在更新最短路的时候,维护每个点是否经由铁路到达1,注意是要所选的铁路最少:

  如果该点已经使用铁路且使用道路距离<=当前距离  update

  如果该点距离<当前距离  update

 

  其实就是要多考虑用道路替换铁路情况(尽管dis不变),不过我的代码写得不是很清晰,包含了更多的情况,只是由于每个城市最多取一条铁路,不影响答案

  最后扫一遍记录使用铁路的结点数, ans = k-cnt

 

  PS:边比较多...听说裸spfa会挂,所以还是dijkstra+heap好写呢

#include <iostream>#include <cstdio>#include <cstdlib>#include <vector>#include <queue>#include <cstring>using namespace std;const int maxn = 1000000+50;const long long inf = ~0llu >> 1;struct Edge{    int u, v;    long long  w;    void init(int u, int v, long long  w) {        this->u = u;    this->v = v;        this->w = w;    }}edge[maxn*4];typedef pair<long long, int> pii;int n, m, k, edgecnt;int head[maxn], next[maxn];long long dis[maxn];bool istrain[maxn], used[maxn];void addEdge(int u, int v, long long w){    edge[edgecnt].init(u, v, w);    next[edgecnt] = head[u];    head[u] = edgecnt++;}void dijkstra(){    bool done[maxn];    priority_queue<pii, vector<pii>, greater<pii> > q;    memset(done, 0, sizeof(done));    for(int i = 1; i <= n; i++)        dis[i] = inf;    dis[1] = 0;    q.push(make_pair(0, 1));    while(!q.empty()) {        pii tmp = q.top();  q.pop();        int u = tmp.second;        if(done[u]) continue;        done[u] = true;        for(int e = head[u]; e != -1; e = next[e]) {            int v = edge[e].v;            if((used[v] && dis[v] == dis[u]+edge[e].w) || dis[v] > dis[u]+edge[e].w) {                dis[v] = dis[u]+edge[e].w;                used[v] = istrain[e];                q.push(make_pair(dis[v], v));            }        }    }}int main(){#ifdef LOCAL    freopen("450D.in", "r", stdin);#endif    memset(head, -1, sizeof(head));    memset(next, -1, sizeof(next));    memset(istrain, 0, sizeof(istrain));    memset(used, 0, sizeof(used));    scanf("%d%d%d", &n, &m, &k);    for(int i = 0; i < m; i++) {        int u, v;        long long w;        scanf("%d%d%lld", &u, &v, &w);        addEdge(u, v, w);        addEdge(v, u, w);    }//  for(int i = 1; i <= n; i++)//      cout << dis[i] << endl;    for(int i = 0; i < k; i++)  {        int v;        long long w;        scanf("%d%lld", &v, &w);        istrain[edgecnt] = true;        addEdge(1, v, w);    }        dijkstra();    int cnt = 0;    for(int i = 2; i <= n; i++)        cnt += used[i];    printf("%d\n", k-cnt);    return 0;}

 

  当场只写了ABC,其中A挂了一发,B因为没考虑f[i]+2p的情况,WA,C题虽然搞出来了...不过耗时近1h

  最后rating很不错,300+,rank+260!!!!!!!!就突然从1200+ ->1500

  D题只看了会,有大概思路,但是最短路都不熟0 0  

 

//写完这个的时候实际上下一场都已经做完了。。。