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

A.切蛋糕

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.小宝的幸运数组

#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.上进的凡凡

#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 << 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]为前缀和数组

s[p-1]-(p-1)为刚开始前面p-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);

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.数羊

#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.买花

#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.黑洞密码

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.建立火车站

（最大值最小化）明显的二分

#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;
}