The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online(2018 青岛网络预选赛)

2023-03-06 08:03:22

A题 A Live Love 原题链接:https://pintia.cn/problem-sets/1036903825309761536/problems/1041155943483625472



#include<bits/stdc++.h>

#include<stdio.h>

#include<iostream>

#include<cmath>

#include<math.h>

#include<queue>

#include<set>

#include<map>

#include<iomanip>

#include<algorithm>

#include<stack>

using namespace std;

#define inf 0x3f3f3f3f

typedef long long ll;

int main()

{

#ifndef ONLINE_JUDGE

    //freopen("in.txt","r",stdin);

#endif // ONLINE_JUDGE

    int t;int n,m;int ans1,ans2;

    scanf("%d",&t);

    while(t--)

    {

        cin>>n>>m;

        n=n-m;

        ans2=m;

        if(m==0)

            ans1=0;

        else if(m<=n)

            ans1=1;

        else ans1=ceil(m*1.0/(n+1));

        cout<<ans2<<" "<<ans1<<endl;

    }

return 0;

}

C题 Halting Problem 原题链接:https://pintia.cn/problem-sets/1036903825309761536/problems/1041156042892824576



#include<bits/stdc++.h>

#include<stdio.h>

#include<iostream>

#include<cmath>

#include<math.h>

#include<queue>

#include<set>

#include<map>

#include<iomanip>

#include<algorithm>

#include<stack>

using namespace std;

#define inf 0x3f3f3f3f

typedef long long ll;

namespace IO {

    const int MT = 10 * 1024 * 1024;  /// 10MB 请注意输入数据的大小！！！

    char IO_BUF[MT];

    int IO_PTR, IO_SZ;

    /// 要记得把这一行添加到main函数第一行！！！

    void begin() {

        IO_PTR = 0;

        IO_SZ = fread (IO_BUF, 1, MT, stdin);

    }

    template<typename T>

    inline bool scan_d (T & t) {

        while (IO_PTR < IO_SZ && IO_BUF[IO_PTR] != '-' && (IO_BUF[IO_PTR] < '0' || IO_BUF[IO_PTR] > '9'))

            IO_PTR ++;

        if (IO_PTR >= IO_SZ) return false;

        bool sgn = false;

        if (IO_BUF[IO_PTR] == '-') sgn = true, IO_PTR ++;

        for (t = 0; IO_PTR < IO_SZ && '0' <= IO_BUF[IO_PTR] && IO_BUF[IO_PTR] <= '9'; IO_PTR ++)

            t = t * 10 + IO_BUF[IO_PTR] - '0';

        if (sgn) t = -t;

        return true;

    }

    inline bool scan_s (char s[]) {

        while (IO_PTR < IO_SZ && (IO_BUF[IO_PTR] == ' ' || IO_BUF[IO_PTR] == '\n') ) IO_PTR ++;

        if (IO_PTR >= IO_SZ) return false;

        int len = 0;

        while (IO_PTR < IO_SZ && IO_BUF[IO_PTR] != ' ' && IO_BUF[IO_PTR] != '\n')

            s[len ++] = IO_BUF[IO_PTR], IO_PTR ++;

        s[len] = '\0';

        return true;

    }

    template<typename T>

    void print(T x) {

        static char s[33], *s1; s1 = s;

        if (!x) *s1++ = '0';

        if (x < 0) putchar('-'), x = -x;

        while(x) *s1++ = (x % 10 + '0'), x /= 10;

        while(s1-- != s) putchar(*s1);

    }

    template<typename T>

    void println(T x) {

        print(x); putchar('\n');

    }

};

using namespace IO;

using namespace std;

char ins[10005];

int a[10005];

int b[10005];

bool vis[10005][300];

int main()

{

#ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

#endif // ONLINE_JUDGE

begin();

    int t;

    scan_d(t);char opt[10];

    int n;

    int v,k;

    int r;

    while(t--)

    {

        memset(vis,0,sizeof(vis));

        scan_d(n);

        r=0;

        int n2=n;

        int cnt=1;

        while(n--)

        {

            scan_s(opt);

            if(opt[1]=='d')

            {

                scan_d(v);

                ins[cnt]=opt[1];

                a[cnt]=v;

                cnt++;

            }

            else if(opt[1]=='e')

            {

                scan_d(v);

                scan_d(k);

                ins[cnt]=opt[1];

                a[cnt]=v;

                b[cnt]=k;

                cnt++;

            }

            else if(opt[1]=='n')

            {

                scan_d(v);

                scan_d(k);

                ins[cnt]=opt[1];

                a[cnt]=v;

                b[cnt]=k;

                cnt++;

            }

            else if(opt[1]=='l')

            {

               scan_d(v);

                scan_d(k);

                ins[cnt]=opt[1];

                a[cnt]=v;

                b[cnt]=k;

                cnt++;

            }

            else if(opt[1]=='g')

            {

                scan_d(v);

                scan_d(k);

                ins[cnt]=opt[1];

                a[cnt]=v;

                b[cnt]=k;

                cnt++;

            }

        }

        int i=1;

        bool  f=1;char op;

        while(i!=(n2+1))

        {

            if(i<=0||i>n2+1){f=0;break;}

            op=ins[i];

            if(op=='d')

            {

                if(!vis[i][r]){vis[i][r]=1;}

                else {f=0;break;}

                r=(r+a[i])%256;

            }

            else if(op=='e')

            {if(!vis[i][r]){vis[i][r]=1;}

                else {f=0;break;}

                if(r==a[i]){i=b[i];continue;}

            }

            else if(op=='n')

            {

                if(!vis[i][r]){vis[i][r]=1;}

                else {f=0;break;}

               if(r!=a[i]){i=b[i];

               continue;}

            }

            else if(op=='l')

            {if(!vis[i][r]){vis[i][r]=1;}

                else {f=0;break;}

               if(r<a[i]){i=b[i];

               continue;}

            }

            else if(op=='g')

            {

                if(!vis[i][r]){vis[i][r]=1;}

                else {f=0;break;}

                if(r>a[i]){i=b[i];

                continue;}

            }

            i++;

        }

        if(f)puts("Yes");

        else puts("No");

    }

return 0;

}

H Traveling on the Axis 原题链接:https://pintia.cn/problem-sets/1036903825309761536/problems/1041156323504345088

队友代码:

#include <bits/stdc++.h>

#include <cstdio>

#include <algorithm>

#include <queue>

#include <cstring>

#include <map>

#include <set>

#include <vector>

#include <iostream>

#include <stack>

#define rep(i,n) for(int i=0;i<(n);i++)

#define mst(x,i) memset(x,i,sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

typedef long long ll;

const int maxn =  1e5+5;

char s[maxn];

ll c[maxn],sumc[maxn],sum0[maxn],sumcc[maxn];

int n;

void solve() {

	n = strlen(s);

	c[0]=0;

	for(int i=1;i<n;i++) {

		if(s[i]==s[i-1]) {

			c[i]=1;

		}else {

			c[i]=0;

		}

	}

	sumc[0]=0;

	for(int i=1;i<n;i++) {

		sumc[i]=sumc[i-1]+c[i];

	}

	if(s[0]=='0') sum0[0]=1;

	else sum0[0]=0;

	for(int i=1;i<n;i++) {

		int f=1-(s[i]-'0');

		sum0[i]=sum0[i-1]+f;

	}

	sumcc[0]=sumc[0];

	for(int i=1;i<n;i++) {

		int f=0;

		if(c[i]) f=i;

		sumcc[i]=sumcc[i-1]+f;

	}

	ll ans=0;

	for(ll i=1;i<=n;i++) {

		ans += i*(i+1)/2;

		ans += sumcc[i-1];

		ans += sum0[i-1];

	}

	cout<<ans<<endl;

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("data.in","r",stdin);

#endif

	int T;

	scanf("%d",&T);

	while(T--) {

		scanf("%s",s);

		solve();

	}

}

K XOR Clique 原题链接:https://pintia.cn/problem-sets/1036903825309761536/problems/1041156503909756928

队友代码:

#include <bits/stdc++.h>

#include <cstdio>

#include <algorithm>

#include <queue>

#include <cstring>

#include <map>

#include <set>

#include <vector>

#include <iostream>

#include <stack>

#define rep(i,n) for(int i=0;i<(n);i++)

#define mst(x,i) memset(x,i,sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

typedef long long ll;

const int maxn = 1e5+5;

int a[maxn],n;

int c[64];

void solve() {

	for(int i=0;i<n;i++) {

		for(int j=31;j>=0;j--) {

			if( (1<<j)&a[i] ) {

				c[j]++;

				break;

			}

		}

	}

	int ans=-1;

	for(int i=0;i<32;i++) ans=max(ans,c[i]);

	cout<<ans<<endl;

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("data.in","r",stdin);

#endif

	int T;

	scanf("%d",&T);

	while(T--) {

		scanf("%d",&n);

		memset(c,0,sizeof(c));

		for(int i=0;i<n;i++) scanf("%d",&a[i]);

		solve();

	}

	return 0;

}

码农公寓

相关文章