其实真的很希望发题解的时候...能带上题目...
现在至至子想考验你，他会给你两个正整数 a 和 b，让你求一个 c 使得 b 为 a 和 c 的等差中项。
------------------------------------------------------------------------------------------------------------------------------------------
模拟
a,b=map(int,input().split()) print(b+b-a)
至至子很喜欢按位与运算。
他会给你两个正整数 a,b，想让你回答他一个整数 c。为了避免 c 过大而搞坏他的脑子，他要求 c<2^63。
由于他喜欢按位与运算，所以请让 c 满足 a&c=b&c（其中 & 为按位与运算）并且让 c 尽可能地大。
可以发现这一定是有解的。
------------------------------------------------------------------------------------------------------------------------------------------
用2^63-1减去二者异或即可
模拟
a,b=map(int,input().split()) x=pow(2,63)-1 print(x-a^b)
链接： https://ac.nowcoder.com/acm/contest/38630/C
至至子很喜欢斐波那契数列，斐波那契数列 Fn
至至子会进行 T 次询问，每次询问给定一个数 ai ，他想让你找到斐波那契数列中距离 ai 最近的一项，即求一个正整数 x 使得在满足 ∣Fx−ai∣ 最小的基础上 x 尽量小。
------------------------------------------------------------------------------------------------------------------------------------------
打表+二分查找
注意1e18的枚举
ll i, n, m, x, y, len, A[106] = { 0,1 }, a, b, c;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
for (m = 2; A[m - 1] <= 1e18; ++m)A[m] = A[m - 1] + A[m - 2];
++m;
for (cin >> n; n; --n) {
cin >> x;
y = lower_bound(A, A + m, x) - A;
a = A[y - 1], b = A[y];
if (x - a <= b - x)cout << y - 1 << endl;
else cout << y << endl;
}
链接： https://ac.nowcoder.com/acm/contest/38630/D
至至子和苏苏子玩游戏。
给定一个序列 a，长度为 n，且满足 1≤a1<a2<⋯<an。
两人轮流对序列进行操作，至至子先手。每人每次选择一个 aia_iai 并让其减一，要求不破坏 1≤a1<a2<⋯<an 的性质，无法操作者输。
假设至至子和苏苏子都绝顶聪明，那么请同样聪明绝顶的你告诉我，最后谁能赢。
至至子和苏苏子玩游戏。
给定一个序列 a，长度为 n，且满足 1≤a1<a2<⋯<an。
两人轮流对序列进行操作，至至子先手。每人每次选择一个 aia_iai 并让其减一，要求不破坏 1≤a1<a2<⋯<an 的性质，无法操作者输。
假设至至子和苏苏子都绝顶聪明，那么请同样聪明绝顶的你告诉我，最后谁能赢。
------------------------------------------------------------------------------------------------------------------------------------------
显然考虑最终结果为： 1 2 3...
则求可以操作的次数： m (每次读入的数 - i)
由奇偶性定胜负
博弈论
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
for (ll n = read(), i = 1, m = 0; i <= n; ++i)m += read() - i;
puts(m&1?"ZZZ":"SSZ");
} 对于 n 个节点有根树（点的编号从 1 到 n），我们设节点 u 的“长链长度”为 hu
即对于叶子节点，其 h 值为 0，否则为所有儿子节点中最大的 h 值 +1。
现给定一棵树的 h1,h2,⋯,hn，请还原该树的形态，或报告无解。如有多棵满足限制的树，输出任意一棵即可，详见输出格式。
其中，叶子节点指没有子节点的节点， son(u) 表示 uuu 节点的儿子节点构成的集合。
------------------------------------------------------------------------------------------------------------------------------------------
用二维表模拟，二维表A[i][j]表示有个i个儿子的数组中第j个数
若拥有最大儿子节点不止一个orA[i]<A[i+1]前面i个的无法支持起后面i+1个节点则输出-1否则模拟输出（注意边界问题）
注意每次的数组清空
思维题
ll n, m, t, a, b, c, d, i, j, N = 1e5 + 2;
vector<vector<ll>>A;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
A.resize(N << 1);
for (t = read(); t; --t) {
d = -1;
for (n = read(), i = 1; i <= n; ++i)c = read(), A[c].push_back(i), d = max(c, d);
a = d;
if (A[d].size() > 1)d = -1;
else for (i = 0; i < d; ++i)if (A[i].size() < A[i + 1].size()) d = -1;
if (d == -1) cout << -1 << endl;
else {
cout << A[a].back() << endl;
for (i = a - 1; i != -1; --i) for (j = 0; j < A[i].size(); ++j)
cout << A[i + 1][min(j, A[i + 1].size() - 1)] << ' ' << A[i][j] << endl;
}
for (i = 0; i <= a; ++i)A[i].clear();
}
} 链接： https://ac.nowcoder.com/acm/contest/38630/F
至至子开有 n 家公司，第 iii 家公司有 ci 个员工，并且在该公司内形成了 ci−1对 直接上下级的关系（注意到 BOSS 是没有直接上级的）。
今天他良心发现想让 这 n 家公司的所有员工排队买票旅游。
然而这些人的等级观念很重——他们约定一个人在排队的时候不能排在其直接或间接上级的前面（若 a 是 b 的直接上级或间接上级， b 是 c 的直接/间接上级，则 a 是 c 的间接上级）。
于是至至子很好奇，一共有多少种符合条件的排队方案呢？由于这个数可能很大，所以请输出答案对 1000000007 取模的结果。
然而这些人的等级观念很重——他们约定一个人在排队的时候不能排在其直接或间接上级的前面（若 a 是 b 的直接上级或间接上级， b 是 c 的直接/间接上级，则 a 是 c 的间接上级）。
于是至至子很好奇，一共有多少种符合条件的排队方案呢？由于这个数可能很大，所以请输出答案对 1000000007 取模的结果。
------------------------------------------------------------------------------------------------------------------------------------------
先用个简单的样例想想：
两条已经确定顺序且 长度为a,b的链子合并出来的新链子有（a+b）! /a! /b! 种情况（n！代表阶乘）
同理如果是a,b,c三条链子合并则可以等同为a，b先合并再同c合并为新链子，一共（a+b+c）!/ a! /b! /c! 种情况
那么现在问题就转化为在第t个公司中以i为boss的链子有多少中情况，显然为树形dp？？？
好吧，其实可以直接记录答案ans的...
最后合并n个公司的所有链子即可
------------------------------------------------------------------------------------------------------------------------------------------
以下代码中A[i]代表i的阶乘%1e9+7，C[i]代表以i为boss的链子长度，e代表总人数
关键在于求逆元以及dfs中思想以及数组的清空（其实这个测评的数据量好像不是很大...）
ll i, n, m, j, k, A[N] = { 1 }, ans = 1, e, C[N], y;
inline ll ni(ll a) {
return pow(a, mod - 2, mod);
}
vector<vector<ll>>biao;
void dfs(ll x) {
while (!biao[x].empty()) {
ll y = biao[x].back();
biao[x].pop_back();
dfs(y);
ans = ans * ni(A[C[y]]) % mod;
C[x] += C[y];
}
ans = ans * A[C[x] - 1] % mod;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
for (i = 1; i <= 1e5; ++i)A[i] = A[i - 1] * i % mod;
n = read();
for (i = 0; i < n; ++i) {
m = read();
e += m;
ans = ans * ni(A[m]) % mod;
C[1] = 1;
biao.resize(m + 1);
for (auto& x : biao)x.clear();
for (j = 2; j <= m; ++j) {
k = read();
C[j] = 1;
biao[k].push_back(j);
}
dfs(1);
}
ans = ans * A[e] % mod;
cout<<ans<<endl;
} ------------------------------------------------------------------------------------------------------------------------------------------
注：以上为关键代码，C++中快读以及头文件如下
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define ll long long
#define endl '\n'
inline ll read() {
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
} 
全部评论
(0) 回帖