2012年 acm-icpc金华现场赛(A,I,J,K)

骑猪看日落 2021-09-16 10:02 311阅读 0赞

## I题 ##

求平方和，大水题

## J题 ##

一个组合数学题  
我用的方法是用两个数组分别存下裤子是某个时是否之前出现过上衣和鞋子， O ( p ) O(p) O(p)

## A题 ##

贪心，先考虑两个元素  
先1后2： a 1 + a 2 + a 1 ∗ b 2 a\_1+a\_2+a\_1\*b\_2 a1\+a2\+a1∗b2  
先2后1：  a 1 + a 2 + b 1 ∗ a 2 a\_1+a\_2+b\_1\*a\_2 a1\+a2\+b1∗a2  
1排在2前面：  a 1 ∗ b 2 < b 1 ∗ a 2 a\_1\*b\_2<b\_1\*a\_2 a1∗b2<b1∗a2  
事实上，我写过更难的题目，[NOIP2012国王游戏][NOIP2012]，然而训练时却一直记不起来

## K题 ##

大模拟，一个很容易想到的简化代码的方法，用0,1,2,3代表方向,然后左转和撞墙都可以进行mod操作

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
    
    int n;
    const int maxn=1e5+7;
    char div1[5];
    char div2[5];
    int s1,s2,t1,t2;
    int k;
    int ma[30][30];
    struct node
    { 
        int x,y;
        int di;
        int v;
    };
    int getdi (char a)
    { 
        if(a=='S') return 2;
        if(a=='N') return 0;
        if(a=='E') return 1;
        return 3;
    }
    node tom;
    node jerry;
    void swapdi(node &a,node &b)
    { 
        swap(a.di,b.di);
    }
    bool check(node &a)
    { 
        if(a.x==0&&a.di==0)  { a.x = 2;return true;}
        if(a.x==n+1&&a.di==2) { a.x -= 2;return true;}
        if(a.y==0&&a.di==3)  { a.y = 2;return true;}
        if(a.y==n+1&&a.di==1) { a.y -= 2;return true;}
        return false;
    }
    void gonext(node &a)
    { 
    
        int t = a.v;
        while(t--)
        { 
        
        if(a.di==1) a.y++;
        else if(a.di==2) a.x++;
        else if(a.di==3) --a.y;
        else if(a.di==0) --a.x;
        if(check(a)) a.di=(a.di+2)%4;   
        // if(tom.x==jerry.x&&tom.y==jerry.y) swapdi(tom,jerry);
        
                // if(check(jerry)) jerry.di=(jerry.di+2)%4;
        }
    }
    int main()
    { 
        while(cin>>n&&n)
        { 
            scanf("%s%d%d",div1,&s1,&t1);
            scanf("%s%d%d",div2,&s2,&t2);
            scanf("%d",&k);
            int t=0;
            tom.v =s1;
            jerry.v = s2;
            tom.x=tom.y=1;
            tom.di=getdi(div1[0]);
    
            jerry.x=jerry.y=n;
            jerry.di=getdi(div2[0]);
    
            while(t<k)
            { 
                gonext(tom);
                gonext(jerry);
                if(tom.x==jerry.x&&tom.y==jerry.y) swapdi(tom,jerry);
                else
                    { 
                        if((t+1)%t2==0) jerry.di=(jerry.di+3)%4;
                        if((t+1)%t1==0) tom.di=(tom.di+3)%4;
                    }
                // printf("%d %d %d %d\n",tom.x,tom.y,jerry.x,jerry.y);
                ++t;
            }
    
            printf("%d %d\n",tom.x,tom.y);
            printf("%d %d\n",jerry.x,jerry.y);
        }
    
    }

[NOIP2012]: https://blog.csdn.net/qq_39239844/article/details/81237710