第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛题解

非常简单的一场比赛,最近做高数做的太痴迷了,一时间都忘记怎么敲代码了

A.切蛋糕
题解:
一个蛋糕分x份,每份就是\frac{1}{x}
分给k个人,要使得每个人分得的蛋糕尽可能相等,那么每个人只有拿\frac{x}{k}\frac{1}{x}或者\frac{x}{k}+1\frac{1}{x},一定与每人每份的平均值\frac{x}{k}的差值小于\frac{1}{x}

题目要求差值小于等于\frac{1}{2^{10}}
那就取分成1024份,每份大小\frac{1}{1024},再分给k个人
分割成2份需要1(2^0)
分割成4份需要3(2^0+2^1)
分割成8份需要7(2^0+2^1+2^2)
所以分割成1024份需要1023=(2^0+2^1+...+2^9)
1023加上最后打包的次数k是小于6000次的
代码:

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int mod = 998244353;
const double pi = 3.1415926535;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
// std::ios::sync_with_stdio(false);

int k;

int main()
{
    scanf("%d", &k);
    printf("%d\n", 1023 + k);

    int p = 1;
    for(int i = 0; i <= 9; i ++){
      for(int j = 0; j < p; j ++)
        printf("1 %d\n", i);
      p <<= 1;
    }

    int a = 1024 / k, b = 1024 % k;
    for(int i = 1; i <= k; i ++){
      printf("2");
      if(i <= b){
        printf(" %d", a + 1);
        for(int i = 0; i <= a; i ++)  printf(" 10");
        printf("\n");
      }
      else{
        printf(" %d", a);
        for(int i = 0; i < a; i ++)  printf(" 10");
        printf("\n");
      }
    }
    return 0;
}

B.小宝的幸运数组
题解:
先记录一下前缀和s[i]
如果一个区间的和模k为0等价于(s[r]-s[l-1])\ mod \ k \ =0
则说明r-l这个区间和模k等于0
所以我们记录下每个前缀和模k第一次出现的位置,扫一遍求最大值即可。

代码:

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int mod = 998244353;
const double pi = 3.1415926535;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
// std::ios::sync_with_stdio(false);

int t;
int n, k;
ll a[maxn], s[maxn];
map<ll, ll> mp;

int main()
{
    scanf("%d", &t);
    while(t --){
      scanf("%d%d", &n, &k);
      memset(s, 0, sizeof(s));
      for(int i = 1; i <= n; i ++){
        scanf("%lld", &a[i]);
        s[i] = (s[i - 1] + a[i]);
        mp[s[i] % k] = -1;
      }
      mp[0] = -1;
      ll ans = -1;
      for(int i = 0; i <= n; i ++){
        ll p = s[i] % k;
        if(mp[p] == -1) mp[p] = i;
        else  ans = max(ans, 1ll * i - mp[p]);
      }
      printf("%lld\n", ans);
    }
    return 0;
}

C.上进的凡凡
题解:
一个长度为n的字符串,不同子串个数有\frac{n(n+1)}{2}
找出每段递增序列的长度,累加求和即可。

代码:

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int mod = 998244353;
const double pi = 3.1415926535;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
// std::ios::sync_with_stdio(false);

int t;
int n;
int a[maxn];

int main()
{
    ll ans = 0, cnt = 0;
    scanf("%d", &n);
    a[0] = -1;
    for(int i = 1; i <= n; i ++)  scanf("%d", &a[i]);
    for(int i = 1; i <= n; i ++){
      if(a[i - 1] <= a[i]){
        cnt ++;
      }
      else{
        ans += cnt * (cnt + 1) / 2;
        cnt = 1;
      }
    }
    ans += cnt * (cnt + 1) / 2;
    printf("%lld\n", ans);
    return 0;
}

D.Seek the Joker I
题解:
巴什博弈,找必败态。

代码:

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int mod = 998244353;
const double pi = 3.1415926535;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
// std::ios::sync_with_stdio(false);

int t;
int n, k;

int main()
{
    scanf("%d", &t);
    while(t --){
      scanf("%d%d", &n, &k);
      puts(n % (1 + k) == 1 ? "ma la se mi no.1!" : "yo xi no forever!");
    }
    return 0;
}

E.Seek the Joker II
题解:
威佐夫博弈板子题
威佐夫博弈:有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。
博弈论

代码:

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int mod = 998244353;
const double pi = 3.1415926535;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
// std::ios::sync_with_stdio(false);

int t;
int n, x;
double a, b;

int main()
{
    scanf("%d", &t);
    while(t --){
      scanf("%d%d", &n, &x);
      a = x - 1;
      b = n - x;
      double r = (sqrt(5) + 1) / 2;
      int d = abs(a - b) * r;
      puts(d == min(a, b) ? "ma la se mi no.1!" : "yo xi no forever!");
    }
    return 0;
}

F.成绩查询ing
题解:
unordered_map + vector模拟
注意:由于询问量过大,输出换行时要用cout<<"/n",不然这题会超时。
cout << endl 中,endl表示的是输出流的一个manipulator,在输出后,还负责将输出流清空
cout << "/n" 则只是完成回车的功能,而不负责清空输出流。

代码:

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int mod = 998244353;
const double pi = 3.1415926535;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
// std::ios::sync_with_stdio(false);


int n, m, op;
struct node{
  int sc;
  int sex;
  int id;
};

unordered_map<string, node> mp;
vector<string> v[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; i ++){
      string name;
      int sc, id, sex;
      cin >> name >> sc >> sex >> id;
      mp[name] = {sc, sex, id};
      v[sc].pb(name);
    }

    for(int i = 0; i <= 100; i ++){
      if(v[i].size() >= 1){
        sort(v[i].begin(), v[i].end());
      }
    }

    cin >> m;
    while(m --){
      cin >> op;
      if(op == 1){
        string x;
        cin >> x;
        cout << mp[x].sc << " " << mp[x].id << " " << mp[x].sex << "\n";
      }
      else{
        int x;
        cin >> x;
        int len = (int)v[x].size();
        if(len >= 1){
          for(int j = 0; j < len; j ++){
            cout << v[x][j] << "\n";
          }
        }
      }
    }
    return 0;
}

G.贪吃的派蒙
题解:
n个人,总共k个食物,s[i]为前缀和数组
派蒙的位置为p、值为pv
那它前面有p-1个人,后面又n-p+1个人
如果p-1>k也就是还没到派蒙食物就拿完了,那派蒙肯定不用洗碗。
接下来前面p-1个人已经到后面了,派蒙现在在第一个。
只要计算接下来所有人吃剩下的数量和除派蒙外所有人最多能吃的数量比较就能判断了。
所以此时食物还剩k-(p-1),所有人每轮吃的数量cnt=pv+n-1
那么循环的轮数为t=\frac{k-(p-1)}{cnt},最后还剩下res = (k-p-1)\ mod\ cnt
除派蒙外所有人最多能吃的数量为sum = t * (s[n]-pv)+s[p-1]-(p-1)
s[p-1]-(p-1)为刚开始前面p-1个人吃的要减去。
如果sum >= res那么显然我们能吃的比派蒙要多,那么肯定能保证派蒙最后洗碗。

代码:

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int mod = 998244353;
const double pi = 3.1415926535;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
// std::ios::sync_with_stdio(false);

int t, n;
ll k;
ll a[maxn], s[maxn];

void solve(){
  int p = 0;
  ll pv = 0;
  for(int i = 1; i <= n; i ++){
    if(pv < a[i]){
      pv = a[i];
      p = i;
    }
  }
  if(p - 1 > k) puts("NO");
  else{
    k -= (p - 1);
    ll cnt = pv + n - 1;
    ll t = k / cnt;
    ll res = k % cnt;
    ll sum = t * (s[n] - pv) + (s[p - 1] - (p - 1));
    puts(sum >= res ? "YES" : "NO");
  }
}

int main()
{
    scanf("%d", &t);
    while(t --){
      memset(s, 0, sizeof(s));
      scanf("%d%lld", &n, &k);
      for(int i = 1; i <= n; i ++)  scanf("%lld", &a[i]), s[i] = s[i - 1] + a[i];
      solve();
    }
    return 0;
}

H.数羊
题解:
找规律发现m只有三种状态
m=0时 \quad ans=n+2
m=1时 \quad ans=2n
其他情况 \quad ans=2^n

代码:

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int mod = 998244353;
const double pi = 3.1415926535;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
// std::ios::sync_with_stdio(false);

int t;
int n, m;
ll f[1005][1005];

ll ksm(ll a, ll b){
  ll ans = 1 % mod;
  while(b){
    if(b & 1) ans = ans * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return ans;
}

int main()
{
    scanf("%d", &t);
    while(t --){
      scanf("%d%d", &n, &m);
      ll ans = 0;
      if(m == 0){
        ans = n + 2;
      }
      else if(m == 1){
        ans = (n << 1);
      }
      else{
        ans = ksm(2ll, n) % mod;
      }
      printf("%lld\n", ans);
    }
    return 0;
}

I.买花
题解:
设每天买p朵花,那么k{\in}[2,15]天买的花个数为p\sum_{i=1}^k{2^{i-1}}=p\left( 2^k-1 \right) = n
也就是只要n能整除\left( 2^k-1 \right)时一定能找到,注意第一天不能取完。
还有注意输出是YE5N0.

代码:

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int mod = 998244353;
const double pi = 3.1415926535;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
// std::ios::sync_with_stdio(false);

int t;
ll n;

int main()
{
    scanf("%d", &t);
    while(t --){
        scanf("%lld", &n);
        int f = 0;
        ll t = 2;
        for(ll i = 1; i <= 15; i ++){
          ll x = (t - 1);
          if(n % x == 0 && i != 1){
            f = 1;
            break;
          }
          t <<= 1;
        }
        puts(f ? "YE5" : "N0");
    }
    return 0;
}

J.这是一题简单的模拟
题解:
直接模拟,没什么好说的。

代码:

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int mod = 998244353;
const double pi = 3.1415926535;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
// std::ios::sync_with_stdio(false);

int n, m, k;
int g[305][305];
int vis[305];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i ++){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        g[a][b] = w;
        g[b][a] = w;
    }
    scanf("%d", &k);
    int ans = inf, x, num;
    while(k --){
      scanf("%d", &num);
      memset(vis, 0, sizeof(vis));
      int st = 0;
      int res = 0, cnt = 0;
      int f = 1;
      for(int i = 1; i <= num; i ++){
        scanf("%d", &x);
        if(!g[st][x] || vis[x] >= 1)  f = 0;
        if(!vis[x]) cnt ++;
        vis[x] ++;
        res += g[st][x];
        st = x;
      }
      if(!g[st][0] || cnt != n) f = 0;
      res += g[st][0];
      if(f)  ans = min(ans, res);
    }

    if(ans == inf)  puts("-1");
    else  printf("%d\n", ans);
    return 0;
}

L.黑洞密码
题解:
模拟,注意最好用int存储,如果用char,直接加的话可能会越界变成负数。
如果要用char的话,先判断大小,减小后再赋值或者直接用unsigned char。
char:-128-127(2^7-1)
unsigned char:0-255(2^8-1)

代码:

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int mod = 998244353;
const double pi = 3.1415926535;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
// std::ios::sync_with_stdio(false);

string s;
int s1[105], s2[105];
int n1, n2;

int main()
{
    cin >> s;
    for(int i = 0; i < 32; i ++){
      if(isdigit(s[i])) s2[++ n1] = s[i];
      else  s1[++ n2] = s[i];
    }

    for(int i = 1; i <= 16; i ++){
      if(s1[i] >= 'A' && s1[i] <= 'Z'){
          s1[i] += s2[i] - '0';
          if(s1[i] > 'Z') s1[i] = s1[i] - 'Z' + 'a';
        }
        else{
          s1[i] += s2[i] - '0';
          if(s1[i] > 'z') s1[i] = s1[i] - 'z' + 'A';
        }
    }

    for(int i = 0; i <= 3; i ++){
      for(int j = 4; j >= 1; j --)
        cout << (char)s1[i * 4 + j];
    }
    cout << endl;
    return 0;
}

K.建立火车站
题解:
(最大值最小化)明显的二分
二分两个站台的距离x,如果两个城市的距离(a[i] - a[i - 1]) > x 说明两个城市间可以增加站台数量
增加\lceil \frac{a\left[ i \right] -a\left[ i-1 \right]}{x} \rceil -1=\lfloor \frac{a\left[ i \right] -a\left[ i-1 \right] +x-1}{x} \rfloor -1个。
最后与k比较,如果cnt <= k则说明枚举的距离太大使得分的站台太少,所以要缩小右边界。

代码:

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int mod = 998244353;
const double pi = 3.1415926535;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
// std::ios::sync_with_stdio(false);

int n;
ll a[maxn], k;

bool check(ll x){
    ll cnt = 0;
    for(int i = 2; i <= n; i ++){
        if((a[i] - a[i - 1]) > x){
            cnt += (a[i] - a[i - 1] + x - 1) / x - 1;
        }
    }
    return cnt <= k;
}

int main()
{
    scanf("%d%lld", &n, &k);
        for(int i = 1; i <= n; i ++){
            scanf("%lld", &a[i]);
        }
        sort(a + 1, a + n + 1);
        ll l = 0, r = 1e18;
        while(l < r){
            ll mid = l + r >> 1;
            if(check(mid))  r = mid;
            else    l = mid + 1;
        }
        printf("%lld\n", r);
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注