A、符合条件的整数
居然没发现这题本来挺简单，很好发现循环节是7，起点给出，终点给出，求出区间长度整除7就是一定存在的数值，那么还有漏掉的，起始端点取余为1，而且终点取余需要大于1，因为左闭右开区间。加上起始点的哪个1。
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(vv) vv.begin(), vv.end()
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int N = 1e5 + 7;
int main() {
ll n = read(), m = read();
ll ans1 = 1ll << n, ans2 = 1ll << m;
ll ans = ans2 - ans1;
ans /= 7;
if (ans1 % 7 == 1 and ans2 % 7 > 1) ++ans;
write(ans);
return 0;
} B、Relic Discovery
抱歉英文劝退题，翻译把我搞懵逼了，2元的运送费是什么鬼……最后群里有人喊了句快乐签到题，我表示题目看不懂，他表示英文简单……直接左右一乘累加求和即可……英文白痴表示这种英文大佬i了i了。
T = int(input())
for _ in range(T):
n = int(input())
ans = 0
for i in range(n):
a,b = map(int,input().split())
ans += a*b
print(ans) C、漂亮的公园
离散化+LCA，暂时还不太会，先搁着）逃ε=ε=ε=┏(゜ロ゜;)┛。
D、石子游戏
博弈，根据题目意思，奇数只能拆分，偶数只能合并。那么根据题目来看最终结束一定是一些一加一个偶数堆。
那么首先我们分析下奇数，举个例子就懂了，5分解成1 4，和分解成2 3，在2 2 1再1 4，步骤+2，下一次还是对手操作，胜负性不改变，所以你会发现奇数没什么用，拆一个奇数，我一定是一个偶数加一个一出来，不是这个方法分的也没意义。这个偶数才是合并的关键，一个偶数和原来有的偶数合并，那么你会发现下次还是你动手……
所以总结博弈要点如下：
1、奇数一定是拆分成1+x
2、奇数拆分出来的偶数，对手下次就可以合并）如果没输的话，又轮到你了，所以拆分奇数对胜负无影响。
3、所以综上1，2可以得到，直接记录起始偶数的数量，康康一直合并偶数谁最后无法合并了，那就输了，哪怕这个人去分奇数。
/*
5
2 3
2 2
1 4 1 3
1 4 1
7
1 6 1
3 4
3 2 2
1 2 2 2 5
*/
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(vv) vv.begin(), vv.end()
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int N = 1e5 + 7;
int main() {
int n = read();
int ans = 1, cnt = 0; // ans = 1 是后面判断奇数不打太多括号
for (int i = 1; i <= n; ++i) {
int x = read();
if (!(x & 1)) ++ans;
else if (x == 1) ++cnt;
}
if (ans & 1 and cnt != n) puts("Alice");
else puts("Bob");
return 0;
} E、凸多边形的划分
一看划分n-2个三角形，有队友还以为是卡特兰数……
最后看出来是个dp的题目，区间dp，因为给出要1-n全部点构成三角形的点权积之和最小。首先假设len-1的三角形点权最小已经求解完毕，那么到len的长度的时候，就是选取一个分割点，和起点终点构成一个新的三角形，并且这个三角形累加进答案还需要最终最小，那么我们二层循环可以枚举区间起点和区间长度以及分割点确定区间最小值，最终一步步向上递推即可得到最大值。
值得注意的是， 全部为
爆了ll，可以考虑开个__int128或者大数，或者py。
E、__int128写法
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(vv) vv.begin(), vv.end()
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(__int128 x) { if (!x) { putchar('0'); return; } char F[40]; __int128 tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int N = 1e5 + 7;
const __int128 INF = 1e30;
ll a[51];
__int128 dp[51][51];
int main() {
int n; cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int len = 3; len <= n; ++len)
for (int i = 1; i + len - 1 <= n; ++i) {
int j = i + len - 1;
dp[i][j] = INF;
for (int k = i + 1; k < j; ++k)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + (__int128)a[i] * a[j] * a[k]);
}
write(dp[1][n]);
return 0;
}
E、大数写法
//大数
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(vv) vv.begin(), vv.end()
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
struct BigInteger {
static const int BASE = 100000000; //和WIDTH保持一致
static const int WIDTH = 8; //八位一存储,如修改记得修改输出中的%08d
bool sign; //符号, 0表示负数
size_t length; //位数
vector<int> num; //反序存
//构造函数
BigInteger(long long x = 0) { *this = x; }
BigInteger(const string& x) { *this = x; }
BigInteger(const BigInteger& x) { *this = x; }
//剪掉前导0，并且求一下数的位数
void cutLeadingZero() {
while (num.back() == 0 && num.size() != 1) {
num.pop_back();
}
int tmp = num.back();
if (tmp == 0) {
length = 1;
}
else {
length = (num.size() - 1) * WIDTH;
while (tmp > 0)
{
length++;
tmp /= 10;
}
}
}
//赋值运算符
BigInteger& operator=(long long x) {
num.clear();
if (x >= 0) {
sign = true;
}
else {
sign = false;
x = -x;
}
do {
num.push_back(x % BASE);
x /= BASE;
} while (x > 0);
cutLeadingZero();
return *this;
}
BigInteger& operator=(const string& str) {
num.clear();
sign = (str[0] != '-'); //设置符号
int x, len = (str.size() - 1 - (!sign)) / WIDTH + 1;
for (int i = 0; i < len; i++) {
int End = str.size() - i * WIDTH;
int start = max((int)(!sign), End - WIDTH); //防止越界
sscanf(str.substr(start, End - start).c_str(), "%d", &x);
num.push_back(x);
}
cutLeadingZero();
return *this;
}
BigInteger& operator=(const BigInteger& tmp) {
num = tmp.num;
sign = tmp.sign;
length = tmp.length;
return *this;
}
//绝对值
BigInteger abs() const {
BigInteger ans(*this);
ans.sign = true;
return ans;
}
//正号
const BigInteger& operator+() const { return *this; }
//负号
BigInteger operator-() const {
BigInteger ans(*this);
if (ans != 0)
ans.sign = !ans.sign;
return ans;
}
// + 运算符
BigInteger operator+(const BigInteger& b) const {
if (!b.sign) {
return *this - (-b);
}
if (!sign) {
return b - (-*this);
}
BigInteger ans;
ans.num.clear();
for (int i = 0, g = 0;; i++) {
if (g == 0 && i >= num.size() && i >= b.num.size())
break;
int x = g;
if (i < num.size())
x += num[i];
if (i < b.num.size())
x += b.num[i];
ans.num.push_back(x % BASE);
g = x / BASE;
}
ans.cutLeadingZero();
return ans;
}
// - 运算符
BigInteger operator-(const BigInteger& b) const {
if (!b.sign) {
return *this + (-b);
}
if (!sign) {
return -((-*this) + b);
}
if (*this < b) {
return -(b - *this);
}
BigInteger ans;
ans.num.clear();
for (int i = 0, g = 0;; i++) {
if (g == 0 && i >= num.size() && i >= b.num.size())
break;
int x = g;
g = 0;
if (i < num.size())
x += num[i];
if (i < b.num.size())
x -= b.num[i];
if (x < 0) {
x += BASE;
g = -1;
}
ans.num.push_back(x);
}
ans.cutLeadingZero();
return ans;
}
// * 运算符
BigInteger operator*(const BigInteger& b) const
{
int lena = num.size(), lenb = b.num.size();
BigInteger ans;
for (int i = 0; i < lena + lenb; i++)
ans.num.push_back(0);
for (int i = 0, g = 0; i < lena; i++) {
g = 0;
for (int j = 0; j < lenb; j++) {
long long x = ans.num[i + j];
x += (long long)num[i] * (long long)b.num[j];
ans.num[i + j] = x % BASE;
g = x / BASE;
ans.num[i + j + 1] += g;
}
}
ans.cutLeadingZero();
ans.sign = (ans.length == 1 && ans.num[0] == 0) || (sign == b.sign);
return ans;
}
//*10^n 大数除大数中用到
BigInteger e(size_t n) const
{
int tmp = n % WIDTH;
BigInteger ans;
ans.length = n + 1;
n /= WIDTH;
while (ans.num.size() <= n)
ans.num.push_back(0);
ans.num[n] = 1;
while (tmp--)
ans.num[n] *= 10;
return ans * (*this);
}
// /运算符 (大数除大数)
BigInteger operator/(const BigInteger& b) const
{
BigInteger aa((*this).abs());
BigInteger bb(b.abs());
if (aa < bb)
return 0;
char* str = new char[aa.length + 1];
memset(str, 0, sizeof(char) * (aa.length + 1));
BigInteger tmp;
int lena = aa.length, lenb = bb.length;
for (int i = 0; i <= lena - lenb; i++) {
tmp = bb.e(lena - lenb - i);
while (aa >= tmp) {
str[i]++;
aa = aa - tmp;
}
str[i] += '0';
}
BigInteger ans(str);
delete[] str;
ans.sign = (ans == 0 || sign == b.sign);
return ans;
}
// %运算符
BigInteger operator%(const BigInteger& b) const {
return *this - *this / b * b;
}
// ++ 运算符
BigInteger& operator++() {
*this = *this + 1;
return *this;
}
// -- 运算符
BigInteger& operator--() {
*this = *this - 1;
return *this;
}
// += 运算符
BigInteger& operator+=(const BigInteger& b) {
*this = *this + b;
return *this;
}
// -= 运算符
BigInteger& operator-=(const BigInteger& b) {
*this = *this - b;
return *this;
}
// *=运算符
BigInteger& operator*=(const BigInteger& b) {
*this = *this * b;
return *this;
}
// /= 运算符
BigInteger& operator/=(const BigInteger& b) {
*this = *this / b;
return *this;
}
// %=运算符
BigInteger& operator%=(const BigInteger& b) {
*this = *this % b;
return *this;
}
// < 运算符
bool operator<(const BigInteger& b) const {
if (sign != b.sign) { //正负，负正
return !sign;
}
else if (!sign && !b.sign) { //负负
return -b < -*this;
}
//正正
if (num.size() != b.num.size())
return num.size() < b.num.size();
for (int i = num.size() - 1; i >= 0; i--)
if (num[i] != b.num[i])
return num[i] < b.num[i];
return false;
}
bool operator>(const BigInteger& b) const { return b < *this; } // > 运算符
bool operator<=(const BigInteger& b) const { return !(b < *this); } // <= 运算符
bool operator>=(const BigInteger& b) const { return !(*this < b); } // >= 运算符
bool operator!=(const BigInteger& b) const { return b < *this || *this < b; } // != 运算符
bool operator==(const BigInteger& b) const { return !(b < *this) && !(*this < b); } //==运算符
// 逻辑运算符
bool operator||(const BigInteger& b) const { return *this != 0 || b != 0; } // || 运算符
bool operator&&(const BigInteger& b) const { return *this != 0 && b != 0; } // && 运算符
bool operator!() { return (bool)(*this == 0); } // ！ 运算符
//重载<<使得可以直接输出大数
friend ostream& operator<<(ostream& out, const BigInteger& x) {
if (!x.sign)
out << '-';
out << x.num.back();
for (int i = x.num.size() - 2; i >= 0; i--) {
char buf[10];
//如WIDTH和BASR有变化,此处要修改为%0(WIDTH)d
sprintf(buf, "%08d", x.num[i]);
for (int j = 0; j < strlen(buf); j++)
out << buf[j];
}
return out;
}
//重载>>使得可以直接输入大数
friend istream& operator>>(istream& in, BigInteger& x) {
string str;
in >> str;
size_t len = str.size();
int start = 0;
if (str[0] == '-')
start = 1;
if (str[start] == '\0')
return in;
for (int i = start; i < len; i++) {
if (str[i] < '0' || str[i] > '9')
return in;
}
x.sign = !start;
x = str.c_str();
return in;
}
}dp[51][51], a[51];
int main() {
js;
BigInteger INF{ "9999999999999999999999999999999999" };
int n; cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int len = 3; len <= n; ++len)
for (int i = 1; i + len - 1 <= n; ++i) {
int j = i + len - 1;
dp[i][j] = INF;
for (int k = i + 1; k < j; ++k)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[j] * a[k]);
}
cout << dp[1][n] << '\n';
return 0;
}
京公网安备 11010502036488号