10月3日 J 组测逝

news/2024/10/3 19:22:30

智障行为+1

T1	T2	T3	T4
50	100	50	0

T1 50pts

【问题描述】
现在有 𝑛 个数字，请你选中一个数字将它异或 𝑘，其余数字都不变。我们希望让 𝑛 个数字的和变得尽可能大，请问这些数字的和最多为多大。

【输入格式】
从文件 xor.in 中读入数据。第一行输入两个正整数 𝑛,𝑘 第二行输入 𝑛 个正整数，其中第 𝑖 个正整数为 𝑎𝑖

【输出格式】
输出到文件 xor.out 中。输出一行一个整数表示答案。

【样例输入1】
7 3
1 2 3 4 5 6 7
【样例输出1】
31

【样例1解释】
将数字 4 异或 3 得到 7，此时整个数组的和变成 31。

【数据范围及约定】
对于 20% 的数据，有 𝑛=1 对于 60% 的数据，有 𝑛≤1000,1≤𝑎𝑖,𝑘≤1000 对于 80% 的数据，有 𝑛≤105,1≤𝑎𝑖,𝑘≤1000 对于 100% 的数据，有 𝑛≤105,1≤ai,𝑘≤109
需要注意的是:我这个天才位运算优先级没搞清。。。
code:

#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#define int long long
#define pii pair<int, int>
#define il inline
#define p_q priority_queue
#define map unordered_map
#define rg registerusing namespace std;const int N1 = 100005;
const int N2 = 1000006;
const int mod = 998244353;namespace first_coming {
#define IOSIZE 100000int precision = 3, POW[10] = {1,      10,      100,      1000,      10000,100000, 1000000, 10000000, 100000000, 1000000000};char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
// #ifdef ONLINE_JUDGE
// #define getchar()                                                         \
//     ((p1 == p2) and                                                       \
//              (p2 = (p1 = ibuf) + fread(ibuf, 1, IOSIZE, stdin), p1 == p2) \
//          ? (EOF)                                                          \
// : (*p1++))
// #define putchar(x)
//     ((p3 == obuf + IOSIZE) && (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf),
//      *p3++ = x)
// #define isdigit(ch) (ch > 47 && ch < 58)
// #define isspace(ch) (ch < 33)
// #endiftemplate <typename T>inline T read() {T s = 0;int w = 1;char ch;while (ch = getchar(), !isdigit(ch) && (ch != EOF))if (ch == 45)w = -1;if (ch == EOF)return 0;while (isdigit(ch))s = s * 10 + ch - 48, ch = getchar();return s * w;}template <typename T>inline bool read(T& s) {s = 0;int w = 1;char ch;while (ch = getchar(), !isdigit(ch) && (ch != EOF))if (ch == 45)w = -1;if (ch == EOF)return 0;while (isdigit(ch))s = s * 10 + ch - 48, ch = getchar();return s *= w, 1;}inline bool read(char& s) {while (s = getchar(), isspace(s));return 1;}inline bool read(char* s) {char ch;while (ch = getchar(), isspace(ch));if (ch == EOF)return 0;while (!isspace(ch))*s++ = ch, ch = getchar();*s = '\000';return 1;}template <typename T>inline void print(T x) {if (x < 0)putchar(45), x = -x;if (x > 9)print(x / 10);putchar(x % 10 + 48);}inline void print(char x) {putchar(x);}inline void print(char* x) {while (*x)putchar(*x++);}inline void print(const char* x) {for (int i = 0; x[i]; i++)putchar(x[i]);}inline bool read(std::string& s) {s = "";char ch;while (ch = getchar(), isspace(ch));if (ch == EOF)return 0;while (!isspace(ch))s += ch, ch = getchar();return 1;}inline void print(std::string x) {for (int i = 0, n = x.size(); i < n; i++)putchar(x[i]);}inline bool read(bool& b) {char ch;while (ch = getchar(), isspace(ch));b = ch ^ 48;return 1;}inline void print(bool b) {putchar(b + 48);}inline bool read(double& x) {int a = 0, b = 0;char ch = getchar();bool f = 0;while (ch < 48 || ch > 57) {if (ch == 45)f = 1;ch = getchar();}while (47 < ch && ch < 58) {a = (a << 1) + (a << 3) + (ch ^ 48);ch = getchar();}if (ch != 46) {x = f ? -a : a;return 1;}ch = getchar();while (47 < ch && ch < 58) {b = (b << 1) + (b << 3) + (ch ^ 48), ch = getchar();}x = b;while (x > 1)        x /= 10;x /= 10;x = f ? -a - x : a + x;return 1;}inline void print(double x) {if (x < 0) {putchar(45), x = -x;}x = round((long double)x * POW[precision]) / POW[precision],print((long long)x), putchar(46), x -= (long long)(x);for (int i = 1; i <= precision; i++)x *= 10, putchar(x + 48), x -= (int)x;}template <typename T, typename... T1>inline int read(T& a, T1&... other) {return read(a) + read(other...);}template <typename T, typename... T1>inline void print(T a, T1... other) {print(a), print(other...);}struct Fast_IO {~Fast_IO() {fwrite(obuf, p3 - obuf, 1, stdout);}} io;template <typename T>Fast_IO& operator>>(Fast_IO& io, T& b) {return read(b), io;}template <typename T>Fast_IO& operator<<(Fast_IO& io, T b) {return print(b), io;}
}namespace second_coming {int fac[N2] = {0};il void Cinit(int p) {fac[0] = 1;for (int i = 1; i < N2; i++) {fac[i] = fac[i - 1] * i % p;}}il int qpow(int a, int b, int p) {int ans = 1;while (b) {if (b & 1) {ans = ans * a % p;}a = a * a % p;b >>= 1;}return ans;}il int C(int n, int m, int p) {if (m > n || m < 0) {return 0;}return fac[n] * qpow(fac[m], p - 2, p) % p * qpow(fac[n - m], p - 2, p) % p;}il int Lucas(int n, int m, int p) {if (!m)return 1;return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p;}il int GCD(int n, int m, int p) {return __gcd(n, m) % p;}il int LCM(int n, int m, int p) {return n * m % p * qpow(GCD(n, m, p), p - 2, p) % p;}
}
using namespace first_coming;
using namespace second_coming;#define debug 0
#define endl '\n'int _test_ = 1;
int n,k;
int a[100005];
namespace third_coming {void init() {cin>>n>>k;int cnt=0;for(int i=1;i<=n;i++){cin>>a[i];cnt+=a[i];}int mx=0;for(int i=1;i<=n;i++){mx=max(mx,cnt-a[i]+(a[i]^k));}cout<<mx;}void solve() {;}void main() {init();solve();}
}signed main() {//  ios::sync_with_stdio(0);//  cin.tie(0);//  cout.tie(0);
#ifdef debug// freopen("xor.in", "r", stdin);// freopen("xor.out", "w", stdout);
#endifthird_coming::main();return 0;
}

T2 100pts

【问题描述】
有一个很大的数字，现在请你通过以下操作让这个数字变得更大。有两种操作： 1. 将数字的每一位都增加 1，如果某一位是 9，则会增加到 0。这种操作可以使用无限次。 2. 将数字的某一位增加 1，如果某一位是 9，则会增加到 0。这种操作至多只能使用一次。请问最多能将这个数字变成多少。

【输入格式】
从文件 num.in 中读入数据。输入一个正整数 𝑛。

【输出格式】
输出到文件 num.out 中。输出一个正整数表示答案。

【样例输入1】
320
【样例输出1】
996
【样例1解释】
先进行 6 次操作 1，变成 986，然后对第二位进行一次操作 2，变成 996。

【数据范围及约定】
【数据范围】对于 10% 的测试点，𝑛<10 对于 20% 的测试点，𝑛<100 对于 40% 的测试点，有 𝑛<10^9 对于 60% 的测试点，有 𝑛<10^18 对于 100% 的测试点，有 𝑛<10^100000

很简单,注意特判（某z姓同学死这里了）

#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#define int long long
#define pii pair<int, int>
#define il inline
#define p_q priority_queue
#define map unordered_map
#define rg registerusing namespace std;const int N1 = 100005;
const int N2 = 1000006;
const int mod = 998244353;namespace first_coming {
#define IOSIZE 100000int precision = 3, POW[10] = {1,      10,      100,      1000,      10000,100000, 1000000, 10000000, 100000000, 1000000000};char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
// #ifdef ONLINE_JUDGE
// #define getchar()                                                         \
//     ((p1 == p2) and                                                       \
//              (p2 = (p1 = ibuf) + fread(ibuf, 1, IOSIZE, stdin), p1 == p2) \
//          ? (EOF)                                                          \
// : (*p1++))
// #define putchar(x)
//     ((p3 == obuf + IOSIZE) && (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf),
//      *p3++ = x)
// #define isdigit(ch) (ch > 47 && ch < 58)
// #define isspace(ch) (ch < 33)
// #endiftemplate <typename T>inline T read() {T s = 0;int w = 1;char ch;while (ch = getchar(), !isdigit(ch) && (ch != EOF))if (ch == 45)w = -1;if (ch == EOF)return 0;while (isdigit(ch))s = s * 10 + ch - 48, ch = getchar();return s * w;}template <typename T>inline bool read(T& s) {s = 0;int w = 1;char ch;while (ch = getchar(), !isdigit(ch) && (ch != EOF))if (ch == 45)w = -1;if (ch == EOF)return 0;while (isdigit(ch))s = s * 10 + ch - 48, ch = getchar();return s *= w, 1;}inline bool read(char& s) {while (s = getchar(), isspace(s));return 1;}inline bool read(char* s) {char ch;while (ch = getchar(), isspace(ch));if (ch == EOF)return 0;while (!isspace(ch))*s++ = ch, ch = getchar();*s = '\000';return 1;}template <typename T>inline void print(T x) {if (x < 0)putchar(45), x = -x;if (x > 9)print(x / 10);putchar(x % 10 + 48);}inline void print(char x) {putchar(x);}inline void print(char* x) {while (*x)putchar(*x++);}inline void print(const char* x) {for (int i = 0; x[i]; i++)putchar(x[i]);}inline bool read(std::string& s) {s = "";char ch;while (ch = getchar(), isspace(ch));if (ch == EOF)return 0;while (!isspace(ch))s += ch, ch = getchar();return 1;}inline void print(std::string x) {for (int i = 0, n = x.size(); i < n; i++)putchar(x[i]);}inline bool read(bool& b) {char ch;while (ch = getchar(), isspace(ch));b = ch ^ 48;return 1;}inline void print(bool b) {putchar(b + 48);}inline bool read(double& x) {int a = 0, b = 0;char ch = getchar();bool f = 0;while (ch < 48 || ch > 57) {if (ch == 45)f = 1;ch = getchar();}while (47 < ch && ch < 58) {a = (a << 1) + (a << 3) + (ch ^ 48);ch = getchar();}if (ch != 46) {x = f ? -a : a;return 1;}ch = getchar();while (47 < ch && ch < 58) {b = (b << 1) + (b << 3) + (ch ^ 48), ch = getchar();}x = b;while (x > 1)        x /= 10;x /= 10;x = f ? -a - x : a + x;return 1;}inline void print(double x) {if (x < 0) {putchar(45), x = -x;}x = round((long double)x * POW[precision]) / POW[precision],print((long long)x), putchar(46), x -= (long long)(x);for (int i = 1; i <= precision; i++)x *= 10, putchar(x + 48), x -= (int)x;}template <typename T, typename... T1>inline int read(T& a, T1&... other) {return read(a) + read(other...);}template <typename T, typename... T1>inline void print(T a, T1... other) {print(a), print(other...);}struct Fast_IO {~Fast_IO() {fwrite(obuf, p3 - obuf, 1, stdout);}} io;template <typename T>Fast_IO& operator>>(Fast_IO& io, T& b) {return read(b), io;}template <typename T>Fast_IO& operator<<(Fast_IO& io, T b) {return print(b), io;}
}namespace second_coming {int fac[N2] = {0};il void Cinit(int p) {fac[0] = 1;for (int i = 1; i < N2; i++) {fac[i] = fac[i - 1] * i % p;}}il int qpow(int a, int b, int p) {int ans = 1;while (b) {if (b & 1) {ans = ans * a % p;}a = a * a % p;b >>= 1;}return ans;}il int C(int n, int m, int p) {if (m > n || m < 0) {return 0;}return fac[n] * qpow(fac[m], p - 2, p) % p * qpow(fac[n - m], p - 2, p) % p;}il int Lucas(int n, int m, int p) {if (!m)return 1;return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p;}il int GCD(int n, int m, int p) {return __gcd(n, m) % p;}il int LCM(int n, int m, int p) {return n * m % p * qpow(GCD(n, m, p), p - 2, p) % p;}
}
using namespace first_coming;
using namespace second_coming;#define debug 1
#define endl '\n'int _test_ = 1;
string s;
namespace third_coming {void init() {cin>>s;}void solve() {string t=s;for(int i=0;i<s.size();i++){if(t[i]!='9') {t[i]++;break;}}while(s[0]!='9'){for(int i=0;i<s.size();i++){s[i]=(s[i]-'0'+1)%10+'0';}}for(int i=1;i<s.size();i++){if(s[i]!='9') {s[i]++;break;}}for(int i=0;i<s.size();i++){if(s[i]>t[i]){cout<<s;exit(0);}if(s[i]<t[i]){cout<<t;exit(0);}}cout<<s;}void main() {init();solve();}
}signed main() {//  ios::sync_with_stdio(0);//  cin.tie(0);//  cout.tie(0);
#ifdef debug// freopen("num.in", "r", stdin);// freopen("num.out", "w", stdout);
#endifthird_coming::main();return 0;
}

T3 50pts

【问题描述】
请你通过若干次除法将一个数字 𝑥 变得不超过 𝑦。

现在有很多个除数可以选择，给定一个长度为 𝑛 的序列 𝑏。表示除数 𝑖 的花费是 𝑏𝑖，你可以用这个除数把 𝑥 变为 (x/i)下取整。每种除数可以使用无限次。

多组询问，每组询问输入两个数 𝑥,𝑦，表示需要使用若干次除法把 𝑥 变得不超过 𝑦，对于每一组询问你都要输出一个答案表示求最小花费，保证题目一定有解。

【输入格式】
从文件 div.in 中读入数据。输入包含 𝑞+2 行。第一行输入两个正整数 𝑛,𝑞。第二行输入 𝑛 个正整数，第 𝑖 个数表示 𝑏𝑖。接下来 𝑞 行，每行两个正整数 𝑥,𝑦，如题意所示。。

【输出格式】
输出到文件 div.out 中。输出 𝑞 行。每行输出一个数，表示对应询问的答案。

【样例输入1】
5 3
4 3 2 2 4
4 3
1 4
5 1
【样例输出1】
2
0
2
【样例1解释】
无

【数据范围及约定】
对于所有的测试点，1≤𝑏𝑖≤109。对于测试点1∼2：1≤𝑛,𝑞,𝑥,𝑦≤10^2。对于测试点3∼4：1≤𝑛,𝑞,𝑥,𝑦≤10^3。对于测试点5∼10：1≤𝑛,𝑞,𝑥,𝑦≤10^5。

一道也不怎么难的问题,思路是预处理+二分，见代码：

#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#define int long long
#define pii pair<int, int>
#define il inline
#define p_q priority_queue
#define map unordered_map
#define rg registerusing namespace std;const int N1 = 100005;
const int N2 = 1000006;
const int mod = 998244353;namespace first_coming {
#define IOSIZE 100000int precision = 3, POW[10] = {1,      10,      100,      1000,      10000,100000, 1000000, 10000000, 100000000, 1000000000};char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
// #ifdef ONLINE_JUDGE
// #define getchar()                                                         \
//     ((p1 == p2) and                                                       \
//              (p2 = (p1 = ibuf) + fread(ibuf, 1, IOSIZE, stdin), p1 == p2) \
//          ? (EOF)                                                          \
// : (*p1++))
// #define putchar(x)
//     ((p3 == obuf + IOSIZE) && (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf),
//      *p3++ = x)
// #define isdigit(ch) (ch > 47 && ch < 58)
// #define isspace(ch) (ch < 33)
// #endiftemplate <typename T>inline T read() {T s = 0;int w = 1;char ch;while (ch = getchar(), !isdigit(ch) && (ch != EOF))if (ch == 45)w = -1;if (ch == EOF)return 0;while (isdigit(ch))s = s * 10 + ch - 48, ch = getchar();return s * w;}template <typename T>inline bool read(T& s) {s = 0;int w = 1;char ch;while (ch = getchar(), !isdigit(ch) && (ch != EOF))if (ch == 45)w = -1;if (ch == EOF)return 0;while (isdigit(ch))s = s * 10 + ch - 48, ch = getchar();return s *= w, 1;}inline bool read(char& s) {while (s = getchar(), isspace(s));return 1;}inline bool read(char* s) {char ch;while (ch = getchar(), isspace(ch));if (ch == EOF)return 0;while (!isspace(ch))*s++ = ch, ch = getchar();*s = '\000';return 1;}template <typename T>inline void print(T x) {if (x < 0)putchar(45), x = -x;if (x > 9)print(x / 10);putchar(x % 10 + 48);}inline void print(char x) {putchar(x);}inline void print(char* x) {while (*x)putchar(*x++);}inline void print(const char* x) {for (int i = 0; x[i]; i++)putchar(x[i]);}inline bool read(std::string& s) {s = "";char ch;while (ch = getchar(), isspace(ch));if (ch == EOF)return 0;while (!isspace(ch))s += ch, ch = getchar();return 1;}inline void print(std::string x) {for (int i = 0, n = x.size(); i < n; i++)putchar(x[i]);}inline bool read(bool& b) {char ch;while (ch = getchar(), isspace(ch));b = ch ^ 48;return 1;}inline void print(bool b) {putchar(b + 48);}inline bool read(double& x) {int a = 0, b = 0;char ch = getchar();bool f = 0;while (ch < 48 || ch > 57) {if (ch == 45)f = 1;ch = getchar();}while (47 < ch && ch < 58) {a = (a << 1) + (a << 3) + (ch ^ 48);ch = getchar();}if (ch != 46) {x = f ? -a : a;return 1;}ch = getchar();while (47 < ch && ch < 58) {b = (b << 1) + (b << 3) + (ch ^ 48), ch = getchar();}x = b;while (x > 1)        x /= 10;x /= 10;x = f ? -a - x : a + x;return 1;}inline void print(double x) {if (x < 0) {putchar(45), x = -x;}x = round((long double)x * POW[precision]) / POW[precision],print((long long)x), putchar(46), x -= (long long)(x);for (int i = 1; i <= precision; i++)x *= 10, putchar(x + 48), x -= (int)x;}template <typename T, typename... T1>inline int read(T& a, T1&... other) {return read(a) + read(other...);}template <typename T, typename... T1>inline void print(T a, T1... other) {print(a), print(other...);}struct Fast_IO {~Fast_IO() {fwrite(obuf, p3 - obuf, 1, stdout);}} io;template <typename T>Fast_IO& operator>>(Fast_IO& io, T& b) {return read(b), io;}template <typename T>Fast_IO& operator<<(Fast_IO& io, T b) {return print(b), io;}
}namespace second_coming {int fac[N2] = {0};il void Cinit(int p) {fac[0] = 1;for (int i = 1; i < N2; i++) {fac[i] = fac[i - 1] * i % p;}}il int qpow(int a, int b, int p) {int ans = 1;while (b) {if (b & 1) {ans = ans * a % p;}a = a * a % p;b >>= 1;}return ans;}il int C(int n, int m, int p) {if (m > n || m < 0) {return 0;}return fac[n] * qpow(fac[m], p - 2, p) % p * qpow(fac[n - m], p - 2, p) % p;}il int Lucas(int n, int m, int p) {if (!m)return 1;return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p;}il int GCD(int n, int m, int p) {return __gcd(n, m) % p;}il int LCM(int n, int m, int p) {return n * m % p * qpow(GCD(n, m, p), p - 2, p) % p;}
}
using namespace first_coming;
using namespace second_coming;#define debug 1
#define endl '\n'int _test_ = 1;
int n,k;
int co[100005];
namespace third_coming {void init() {cin>>n>>k;memset(co,0x3f,sizeof(co));for(int i=1;i<=n;i++){cin>>co[i];}int mn=0x3f3f3f3f3f3f3f3f;for(int i=1e5;i>=1;i--){mn=min(mn,co[i]);co[i]=mn;}for(int i=2;i<=n;i++){for(int j=2;j * i<=1e5;j++){co[j * i]=min(co[j * i],co[i]+co[j]);// t*=i;}}mn=0x3f3f3f3f3f3f3f3f;for(int i=1e5;i>=1;i--){mn=min(mn,co[i]);co[i]=mn;}while(k--){int x,y;cin>>x>>y;if(x<=y) {cout<<"0\n";continue;}int l=1,r=1e5;int mid=50000;int ans=0;while(l<=r){// cout<<l<<' '<<r<<endl;mid=(l+r)>>1;if(x/mid<=y){ans=mid;r=mid-1;}else l=mid+1;}cout<<co[ans]<<endl;}}void solve() {}void main() {init();solve();}
}signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef debug// freopen("div.in", "r", stdin);// freopen("div.out", "w", stdout);
#endifthird_coming::main();return 0;
}

T4 0pts

【问题描述】
对于一个字符串而言，假设有某一个字母只出现过一次，那么我们就称它为“坏子串”。例如 "abb" ， "bcdde" 就是坏子串，而 "aa" ， "abcacb" 不是坏字符串。
给一个字符串，请问有多少个子串是坏子串。

【输入格式】
从文件 string.in 中读入数据。输入一个仅由小写字母组成的字符串。

【输出格式】
输出到文件 string.out 中。输出一个整数表示答案。

【样例输入1】
abba
【样例输出1】
8
【样例1解释】
"a"、"ab"、"abb"、"b"、"bba"、"b"、"ba"、"a"共有8个坏子串。

【数据范围及约定】
对于 1−4 测试点，保证字符串长度不超过 200。对于 5−8 测试点，保证字符串长度不超过 2000。对于 9−10 测试点，保证字符串长度不超过 105 且字符种类数不超过 2。对于 11−12 测试点，保证字符串长度不超过 105 。对于 13−14 测试点，保证字符串的字符种类不超过 2。对于 15−20 测试点，保证字符串长度不超过 5 × 106 。

好吧我这道题不会，会的私信我一下谢谢（汗

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.ryyt.cn/news/67446.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈，一经查实，立即删除！