2017 gdut学校試合の初戦の題解

タイトルのソース:http://www.gdutcode.sinaapp.com/contest.php?cid=1054
Problem A：An easure problem
标准サインは问题になりますが、直接にAcceptを出力します。A大文字でない人はどのような気持ちですか？

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int main()
{
    puts("Accept");
    return 0;
}

Problem B：Tmkはスープご飯を食べます。
解析：規則的なシーケンスです。公式を押していません。直接的に打つ表です。公式は（n/4＋1）＊5+（n%4＋1）です。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 10050;
int a[maxn];
int main()
{
    a[0] = 6;
    for(int i=1;i1]+1;
        if(i%4==0)
            a[i]++;
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        printf("%d
",a[n]);
    }
    return 0;
}

Problem C：進撃の調査兵団
二分の答え、二分の答えが出たら、二分の検索は各シーケンスの中でどれぐらいの小さいのが彼に等しくて、stlはいいものですか？

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1e5+100;
int a[maxn];
int b[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m,q;
        scanf("%d %d %d",&n,&m,&q);
        for(int i=0;iscanf("%d",&a[i]);
        for(int i=0;iscanf("%d",&b[i]);
        while(q--)
        {
            int l1,r1,l2,r2,k;
            scanf("%d %d %d %d %d",&l1,&r1,&l2,&r2,&k);
            int l = min(a[l1],b[l2]),r = max(a[r1],b[r2]);
            while(lint mid = l+((r-l)/2);
                int pos1 = lower_bound(a+l1,a+r1+1,mid)-a;
                if(a[pos1]==mid)
                    pos1++;
                int pos2 = lower_bound(b+l2,b+r2+1,mid)-b;
                if(b[pos2]==mid)
                    pos2++;
                if(pos1+pos21;
                else
                    r = mid;
            }
            printf("%d
",l);
        }
    }
    return 0;
}

Problem D：TMKの航写画像
重点がないので、可能な線分は全部n*(n-1)/2です。直線ですから、二つの点を列挙して、他の点と交わるかどうかを判断します。もし交わるとans–

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 2e5+10;
struct point
{
    int x,y;
}a[maxn];
int n,m;
int x_mul(point p0,point p1,point p2)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int main()
{
    //freopen("a.in","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=0;iscanf("%d %d",&a[i].x,&a[i].y);
        int ans = n*(n-1)/2;
        for(int i=0;ifor(int j=i+1;jfor(int k=0;kif(k>=i && k<=j)
                        continue;
                    if(x_mul(a[k],a[i],a[j])==0)
                        ans--;
                }
            }
        }
        printf("%d
",ans);
    }
    return 0;
}

Problem E：遠回り
解析：dp問題、dp[i][n]は点iの長さがnであるかどうかを表しています。状態移行方程式は、dp[tmp.v][tt]=dp[i]、[tt-tmp.w]で、tmp.vからiまでの間にtmp.wの長さがあります。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 5000+40;
struct node
{
    int v,w;
    node() {}
    node(int _v,int _w)
    {
        v = _v;
        w = _w;
    }
};
vectorG1[maxn],G2[maxn];
int dp[maxn][maxn];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        int n,m,k;
        scanf("%d %d %d",&n,&m,&k);
        for(int i=1;i<=n;i++)
            G1[i].clear(),G2[i].clear();
        while(m--)
        {
            int u,v,l;
            scanf("%d %d %d",&u,&v,&l);
            if(u!=v)
            {
                if(u>v)
                    swap(u,v);
                G1[u].push_back(node(v,l));
            }
            else
                G2[u].push_back(node(v,l));
        }
        dp[1][0] = 1;
        for(int i=1;i<=n;i++)
        {
            for(unsigned j=0;jfor(int tt=tmp.w;tt<=k;tt++)
                    dp[i][tt] |= dp[i][tt-tmp.w];
            }
            for(unsigned j=0;jfor(int tt=tmp.w;tt<=k;tt++)
                    dp[tmp.v][tt] |= dp[i][tt-tmp.w];
            }
        }
        int ans = -1;
        for(int i=0;i<=k;i++)
        {
            if(dp[n][i])
                ans = i;
        }
        printf("%d
",ans);
    }
    return 0;
}

Problem F：パスワードロック
解析：歯車ごとに所望の位置に移動する最低ステップ数は、min((Ai-ai+10)%(ai-i+10)%10です。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 10050;
int a[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int ans = 0;
        while(n--)
        {
            int a1,b1,c1,d1;
            int a2,b2,c2,d2;
            scanf("%d %d %d %d",&a1,&b1,&c1,&d1);
            scanf("%d %d %d %d",&a2,&b2,&c2,&d2);
            ans += min((a1-a2+10)%10,(a2-a1+10)%10);
            ans += min((b1-b2+10)%10,(b2-b1+10)%10);
            ans += min((c1-c2+10)%10,(c2-c1+10)%10);
            ans += min((d1-d2+10)%10,(d2-d1+10)%10);
        }
        printf("%d
",ans);
    }
    return 0;
}

知識は分解に由来する。
尺取保守の答え

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1e6+10;
char a[maxn];
int vis[100];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        scanf("%s %d",a,&k);
        n = strlen(a);
        int ans = 0;
        int l = 0,r = 0,cnt = 0;
        memset(vis,0,sizeof(vis));
        while(n-l>ans)
        {
            while(rif(vis[a[r]-'A'])
                    vis[a[r]-'A']++;
                else
                {
                    if(cnt+1>k)
                        break;
                    else
                        cnt++;
                    vis[a[r]-'A']++;
                }
                r++;
            }
            if(cnt == k)
                ans = max(ans,r-l);
            vis[a[l]-'A']--;
            if(vis[a[l]-'A']==0)
                cnt--;
            l++;
        }
        printf("%d
",ans);
    }
    return 0;
}

Problem H：正方形を探します。
解析：一点を見つけて、正方形の長さを列挙して、合法かどうかを判断する。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1e6+10;
char a[25][25];
bool slove(int x,int y,int n)
{
    for(int i=x;i<=x+n;i++)
    {
        if(a[i][y]!='#')
            return false;
        if(a[i][y+n]!='#')
            return false;
    }
    for(int i=y;i<=y+n;i++)
    {
        if(a[x][i]!='#')
            return false;
        if(a[x+n][i]!='#')
            return false;
    }
    return true;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d %d",&n,&m);
        for(int i=0;iscanf("%s",a[i]);
        int flag = 0;
        for(int i=0;ifor(int j=0;jif(a[i][j]=='#')
                {
                    for(int k=1;k<=n-1-i;k++)
                    {
                        if(i+k>=n || j+k>=n)
                            break;
                        if(slove(i,j,k))
                            flag = 1;
                    }
                }
            }
        }
        if(flag)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}