程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces Round #261 (Div. 2)

Codeforces Round #261 (Div. 2)

編輯：C++入門知識

Codeforces Round #261 (Div. 2)

A. Pashmak and Garden

題意：已知兩個頂點的坐標，如果能推斷出另外兩個頂點則輸出（special judge）。如果這兩個頂點不是構成正方形的兩個頂點，

則輸出-1。

水題，1A，不多說。

#include
#include
#include
#include

using namespace std;

int main()
{
    int x1,x2,y1,y2,flag,x3,y3,x4,y4,l;
    while(scanf("%d%d%d%d",&x1,&y1,&x2,&y2)!=EOF)
    {
        int t1 = fabs(x2-x1);
        int t2 = fabs(y2-y1);
        flag = 0;
        if(!t1)
        {
            l = t2;
            x3 = x4 = x1+t2;
            y3 = y1;
            y4 = y2;
        }
        else if(!t2)
        {
            l = t1;
            y3 = y4 = y1+t1;
            x3 = x1;
            x4 = x2;
        }
        else
        {
            if(t1!=t2) flag = 1;
            else
            {
                l = t1;
                x3 = x1;
                y3 = y2;
                x4 = x2;
                y4 = y1;
            }
        }
        if(flag) printf("-1\n");
        else printf("%d %d %d %d\n",x3,y3,x4,y4);
    }
    return 0;
}

B. Pashmak and Flowers

題意：

有n朵花，每朵有個beauty值。問能找到的beauty值的最大差異是多少?選擇具有最大差異的兩朵花有幾種方案?

輸出這兩個值。

只要統計最大值和最小值，以及最大值與最小值的個數cnt1、cnt2即可，方案數為cnt1*cnt2。

特判：如果最大差異值為0，即最大值等於最小值時，方案數為n*(n-1)/2。

#include
#include
#include
#define maxn 200010
#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;
int f[maxn];

int main()
{
    int n,maxv,minv;
    ll cnt1,cnt2,ans;
    scanf("%d",&n);
    minv = INF,maxv = -INF;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&f[i]);
        if(f[i]>maxv) maxv = f[i];
        if(f[i]




C. Pashmak and Buses


題意：
有n個學生，k輛bus，d天。要安排n個學生d天乘坐的bus，使得沒有兩個學生的車d天都是相同的。



算法：
首先，每天每個學生有k種乘坐方案（1-k車)，那麼d天總共能有k^d種不同的乘坐方案。
如果n>k^d，則必有兩個學生是行程安排相同的。（容斥原理）==>此種情況輸出-1.
由於k很大，如果一直乘方或者快速冪即使用long long也會溢出，但是如果只要判斷其與n的大小，
而n最大為1000，則設一個>1000且在int范圍內的INF即可，一旦大於INF，則break。



其次，麻煩的是要輸出n個學生的每天的車的安排情況。
開始用全排列next_permutation自己想了一種方案，改了很久，寫了快200行，但是有問題。後來看了別人的寫法，頓感無比精妙!
由於n個學生必定存在不同的方案，此時利用 n%k+1和n/=k的序列一定會不同來構造ans[i][j](第i天第j個
學生乘坐幾號車)



#include
#include
#include
#define INF 10000000
#define maxn 1010

using namespace std;
int ans[maxn][maxn];

int main()
{
    int n,k,d;
    while(scanf("%d%d%d",&n,&k,&d)!=EOF)
    {
        int res = 1;
        for(int i=1;i<=d;i++)
        {
            res = res*k;
            if(res>INF)
            {
                res = INF;
                break;
            }
        }
        if(res



D. Pashmak and Parmida's problem
題意：
定義f(l,r,x)為i屬於[l，r]區間，a[i]=x的個數。
求滿足f（1，i,a[i])>f(j,n,a[j] )且in?≤?10⁶



算法：
統計a[i]左邊與它相等的個數和a[j]右邊與它相等的值的個數都要掃一遍。
因為要計數，暴力方法不是費時（兩種循環）就是費內存無法處理（a[i]最大有10^9，數組開不下）。
用map神器來計數O(∩_∩)O哈！



然後用樹狀數組來存ri[i]的個數。
從1-n掃描，每次先把當前的ri[i]值更新即個數-1.保證下標為j>i.即此時j=i+1.....i+n
然後找i+1的ri值中比le[i]值小的個數。



#include
#include
#include
#include
#define maxn 1000010

using namespace std;

typedef long long ll;
map s;
int le[maxn],ri[maxn],c[maxn],n,a[maxn];

int lowbit(int x)
{
    return x&(-x);
}
int que(int pos)
{
    int sum = 0;
    while(pos>0)
    {
        sum+=c[pos];
        pos -= lowbit(pos);
    }
    return sum;
}
void update(int pos,int v)
{
    while(pos<=n)
    {
        c[pos]+=v;
        pos += lowbit(pos);
    }
}

int main()
{
    ll ans;
    while(scanf("%d",&n)!=EOF)
    {
        s.clear();
        memset(le,0,sizeof(le));
        memset(ri,0,sizeof(ri));
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
        {
            s[a[i]]++;
            le[i] = s[a[i]];
        }
        s.clear();
        for(int j=n;j>=1;j--)
        {
            s[a[j]]++;
            ri[j] = s[a[j]];
        }
        for(int i=n;i>=1;i--)
            update(ri[i],1);
        ans = 0;
        for(int i=1;i<=n;i++)
        {
            update(ri[i],-1);
            ans+=que(le[i]-1);
        }
        printf("%I64d\n",ans);
    }
    return 0;
}


E. Pashmak and Graph
題意：n個點m條邊的有向圖，求一條路徑，使得路徑上的邊權值嚴格單調遞增且路徑上的邊數最多。
輸出最大邊數。



算法：
首先按邊權從小到大排序，沒有相等的邊時，可以直接更新dp[e[i].to] = max(dp[e[i].fr]+1,dp[e[i].to]。
但是如果有相等的邊，這樣一步一步的更新會把數量相加即把相等的邊算在一條路徑上的邊數上。
所以我們要設一個中間數組f，讓所有邊權相等的邊先從dp[e[i].fr]那裡轉移再一起更新。



#include
#include
#include
#include
#define maxn 300010

using namespace std;

int dp[maxn],n,m,f[maxn];
struct node
{
    int fr,to,v;
}e[maxn];

bool cmp(node x,node y)
{
    return x.v