Codeforces Round #257 (Div. 2) A/B/C/D

Codeforces Round #257 (Div. 2) A/B/C/D

前三題早就寫好了，一直在糾結D

A. Jzzhu and Children

題意：就是簡單的模擬，給排成一隊的孩子分發糖果，每個孩子有至少要得到的糖果數。

然後每次給隊頭的孩子分發m個糖果，如果他已經得到了足夠的糖果（大於等於他想得到的

最少糖果數）那麼他就出隊，否則他就去隊尾。問最後一個孩子的編號。

算法:隊列模擬，水題~

#include
#include
#include
#include

using namespace std;

struct node
{
    int v,id;
};

queue q;

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        while(!q.empty()) q.pop();
        node cur;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&cur.v);
            cur.id = i;
            q.push(cur);
        }
        int flag = 0;
        while(!q.empty())
        {
            if(q.size()==1)
                flag = 1;
            node x,next;
            x = q.front();
            q.pop();
            if(flag==1)
            {
                printf("%d\n",x.id);
                break;
            }

            int t = x.v-m;
            if(t>0)
            {
                next.v = t;
                next.id = x.id;
                q.push(next);
            }
        }
    }
    return 0;
}

題意： 現在輸入x和y，求fn%1000000007 (10⁹?+?7)。

算法：

就是找到一個循環節

f(i) = f(i-1) - f(i-2)

f(i+1) = -f(i-2)

f(i+2) = -f(i-1)

f(i+3) = f(i-2) - f(i-1)

f(i+4) = f(i-2)

f(i+5) = f(i-1)

f(i+6) = f(i-1) - f(i-2) = f(i)

以6為一個循環周期。

注意輸入x 和 y 時就要處理>mod則 %mod，小於mod 則+mod後再模mod。避免後面溢出。

注意n = 1 和2 的時候直接輸出。

#include
#include
#include

using namespace std;

typedef long long ll;
const ll mod = 1000000007LL ;
ll a[10];

ll f1,f2,n;

int main()
{
    while(scanf("%I64d%I64d",&f1,&f2)!=EOF)
    {
        scanf("%I64d",&n);
        int x = 0;
        if(f1>mod) f1%=mod;
        if(f1<0) f1 = (f1+mod)%mod;
        if(f2>mod) f2%=mod;
        if(f2<0) f2 = (f2+mod)%mod;
        a[x++] = f2-f1;
        a[x++] = -f1;
        a[x++] = -f2;
        a[x++] = f1-f2;
        a[x++] = f1;
        a[x++] = f2;
        for(int i=0;i

C. Jzzhu and Chocolate


題意：
把一塊n*m格的巧克力切k刀，每次只能沿著橫線和豎線切，不能一格分成兩部分。如果不能切k刀，輸出-1.如果能，
問k刀後，最小的那塊巧克力最多含有多少個格子。



算法：
1、一塊n*m的巧克力最多能切n-1+m-1即n+m-2刀，如果k>n+m-2則輸出-1.
2、由(n/3)*m>(n/2)*(m/2)即把一邊切兩刀比兩邊各切一刀得到的面積大，得到貪心策略：如果一邊能切，
盡量先切一邊再切另一邊。
但是先切哪一邊使得結果最優呢，兩種情況分別計算取最大值就好。



P.S：突然發現，這題的程序和#32的那道神題的錯誤代碼一模一樣的思路呢，用這種思路過了那題的人們，
OMG!!!



#include
#include
#include

using namespace std;

typedef long long ll;
ll n,m,k,s1,s2;

int main()
{
    while(scanf("%I64d%I64d%I64d",&n,&m,&k)!=EOF)
    {
        if(k > n+m-2)
        {
            printf("-1\n");
            continue;
        }
        if(k<=m-1)
            s1 = n*(m/(k+1));
        else
            s1 = n/(k-m+2);
        if(k<=n-1)
            s2 = m*(n/(k+1));
        else
            s2 = m/(k-n+2);
        printf("%I64d\n",max(s1,s2));
    }
    return 0;
}


D. Jzzhu and Cities


題意：明天早上來寫，今天要回去了。。。



#include
#include
#include
#include
#define maxm 300010
#define maxn 100010
#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;
struct E
{
    int to,next;
    ll w;
}e[maxm<<2];
int head[maxn],cnt,n,c[maxn],mp[maxn];
bool vis[maxn];
ll dis[maxn];
priority_queue q;

void init()
{
    memset(mp,0x3f,sizeof(mp));
    memset(c,0,sizeof(c));
    memset(vis,0,sizeof(vis));
    memset(head,-1,sizeof(head));
    cnt = 0;
}
void add(int x,int y,ll z)
{
    e[cnt].to = y;
    e[cnt].w = z;
    e[cnt].next = head[x];
    head[x] = cnt++;
    e[cnt].to = x;
    e[cnt].w = z;
    e[cnt].next = head[y];
    head[y] = cnt++;
}

void spfa()
{
    for(int i=1;i<=n;i++)
        dis[i] = INF;
    while(!q.empty())
        q.pop();
    dis[1] = 0;
    c[1] = 1;
    q.push(1);
    vis[1] = true;
    while(!q.empty())
    {
        int u = q.top();
        q.pop();
        vis[u] = 0;
        for(int k = head[u];k!=-1;k=e[k].next)
        {
            int v = e[k].to;
            if(dis[v]>dis[u]+e[k].w)
            {
                dis[v] = dis[u]+e[k].w;
                c[v] = c[u];
                if(!vis[v])
                {
                    q.push(v);
                    vis[v] = true;
                }
            }
            else if(dis[v]==dis[u]+e[k].w)
            {
                c[v]+=c[u];
                if(c[v]>2) c[v] = 2;
            }
        }
    }
}

int main()
{
    int u,v,m,k,s,y,sum;
    ll w;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        init();
        for(int i=0;iy)
                mp[s] = y;
        }
        sum = 0;
        for(int i=1;i<=n;i++)
        {
            if(mp[i]!=INF)
            {
                add(1,i,mp[i]);
                sum++;
            }
        }
        spfa();
        for(int i=1;i<=n;i++)
        {
            if(mp[i]!=INF)
            {
                if(dis[i]1)
                    sum--;
            }

        }
        printf("%d\n",k-sum);
    }
    return 0;
}