2021牛客暑期多校训练营3
B
思维题，难在模型的转化。
对于一个矩阵，将其理解为一个二分图：行和列。
此时，对于每一个点，它就是二分图里的边：连接一个行和一个列。
如果我选择一些点，使得所有的行和列上都存在点，这就是解的必要条件。
但似乎只靠这一条件并不充分，不过能过。
#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 5e3;
const int mod = 1e9 + 7;
ll n, m, a, b, c, d, p;
struct node {
int x, y;
ll w;
bool operator< (const node & o)const{
return w < o.w;
}
} ar[N * N + 1];
int fa[N * 2 + 1];
inline void init(int n) {
for (int i = 1; i <= n; ++i) fa[i] = i;
}
inline int Find(int x) {
if (x != fa[x]) fa[x] = Find(fa[x]); //路径压缩
return fa[x];
}
inline void merge(int x, int y) { fa[Find(y)] = Find(x); }
signed main() {
sc(n), sc(m), sc(a), sc(b), sc(c), sc(d), sc(p);
if (n == 0 or m == 0) return cout << 0, 0;
ar[0].w = a;
rep(i, 1, n) rep(j, 1, m) {
int id = m * (i - 1) + j;
ar[id] = {i, j,
(ar[id - 1].w * ar[id - 1].w * b + ar[id - 1].w * c + d) % p};
}
sort(ar + 1, ar + 1 + m * n);
init(n + m);
ll res = 0, cnt = 0;
rep(i, 1, n * m) {
if (Find(ar[i].x) != Find(ar[i].y + n))
res += ar[i].w, ++cnt, merge(ar[i].x, ar[i].y + n);
if (cnt == n + m - 1) break;
}
pr(res);
return 0;
}
按这样答案不会出错，不过这一选出来的点是无法满足的，但对于这一答案，可能一定存在满足的解。
一组数据：
8 9 9 6 1 5 7
E
队友写的，核心思路是递推第二个数
#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> g;
const int N = 1e6 + 5;
int a[N];
signed main(){
int t, n;
cin >> t;
for (int k = 2; k <= 1e6; ++k) {
a[1] = k;
for (int i = 2; i <= 60 ; ++i) {
a[i] = k * k * a[i - 1] - a[i - 2];
if(a[i] > 1e18 || a[i] < 0) break;
g.push_back(a[i]);
}
}
sort(g.begin(),g.end());
while(t--){
cin >> n;
cout << upper_bound(g.begin(), g.end(), n) - g.begin() + 1 << '\n';
}
return 0;
} F
大模拟。
我的思路是枚举取值后，再枚举逆波兰表达式。
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
int n;
double tar;
vector<vector<int>> res;
const double eps = 1e-6;
int opc[] = {'+', '-', '*', '/'};
inline bool isOper(int x) { // 是不是运算符
return x == '+' || x == '-' || x == '*' || x == '/';
}
inline bool isInt(double x) { // 是不是整数
return fabs(x - int(x)) <= eps || fabs(x - ceil(x)) <= eps;
}
inline bool eq(double x) { return fabs(x - tar) <= eps; } // 等于结果
inline bool cal(double a, double b, int op, double &res) { // 计算一个小算式
if (op == '/') {
res = a / b;
if (!isInt(res)) return 1;
} else if (op == '*')
res = a * b;
else if (op == '+')
res = a + b;
else
res = a - b;
return 0;
}
int deal(vector<int> a) { //计算一个逆波兰表达式
stack<double> st;
double res = 0;
bool f = 0;
for (int i : a) {
if (!isOper(i))
st.push(i);
else {
if (st.size() < 2) return 0; // 鲁棒性
double x = st.top();
st.pop();
double y = st.top();
st.pop();
if (i == '/' && fabs(y) <= eps) return 0; // 避免除零
if (cal(x, y, i, res)) f = 1; // 出现分数解
st.push(res);
}
}
if (st.size() > 1) return 0; // 鲁棒性
if (abs(res - tar) > eps) return 0;
return 1 + f;
// 0 : 不为 m
// 1 : 为m 但无分数
// 2 : 为m 且有分数
}
void dfs(vector<int> &a, vector<int> &pre, int &status, int ch = 0) {
// 采用引用 + 回溯 枚举逆波兰表达式 避免MLE
if (status == 1) return; // 一旦出现非分数解，一切都不用算了
if (a.size() == n + n - 1 and pre.empty()) {
// 长度合法且所有数字都放进来了
int r = deal(a);
if (r and status == 0) // 出现合法解
status = r;
else if (status == 2 and r == 1) // 出现无分数解
status = r;
return;
}
if (pre.size()) {
int c = pre.back();
a.push_back(c);
pre.pop_back();
dfs(a, pre, status, ch);
a.pop_back(); // 回溯
pre.push_back(c);
}
int num = a.size() - ch;
if (ch < num - 1) { // 可以加运算符
rep(i, 0, 3) { // 枚举加入的运算符
a.push_back(opc[i]);
dfs(a, pre, status, ch + 1);
a.pop_back(); // 回溯
}
}
}
bool chk(vector<int> a) {
int f = 0;
do { // 枚举数字出现顺序
vector<int> l, r = a;
dfs(l, r, f);
if (f == 1) return 0;
} while (next_permutation(a.begin(), a.end()));
return f == 2;
}
int main() {
cin >> n >> tar;
if (n == 1) {
cout << 0;
return 0;
} else if (n == 2) { // 懒得写dfs
rep(a, 1, 13) rep(b, a, 13) {
vector<int> num{a, b};
if (chk(num)) res.push_back(num);
}
} else if (n == 3) {
rep(a, 1, 13) rep(b, a, 13) rep(c, b, 13) {
vector<int> num = {a, b, c};
if (chk(num)) res.push_back(num);
}
} else {
rep(a, 1, 13) rep(b, a, 13) rep(c, b, 13) rep(d, c, 13) {
vector<int> num = {a, b, c, d};
if (chk(num)) res.push_back(num);
}
}
cout << res.size() << '\n';
for (vector<int> &v : res) {
for (int &i : v) cout << i << ' ';
cout << '\n';
}
return 0;
} J
对于所有的间色三角形的三边，要么是黑白白，要么是黑黑白，也就是说，一个间色三角形，有两个异色角。
所以
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 8007;
unsigned z1, z2, z3, z4, b, u;
unsigned get() {
b = ((z1 << 6) ^ z1) >> 13;
z1 = ((z1 & 4294967294U) << 18) ^ b;
b = ((z2 << 2) ^ z2) >> 27;
z2 = ((z2 & 4294967288U) << 2) ^ b;
b = ((z3 << 13) ^ z3) >> 21;
z3 = ((z3 & 4294967280U) << 7) ^ b;
b = ((z4 << 3) ^ z4) >> 12;
z4 = ((z4 & 4294967168U) << 13) ^ b;
return (z1 ^ z2 ^ z3 ^ z4);
}
bool read() {
while (!u) u = get();
bool res = u & 1;
u >>= 1;
return res;
}
void srand(int x) {
z1 = x;
z2 = (~x) ^ 0x233333333U;
z3 = x ^ 0x1234598766U;
z4 = (~x) + 51;
u = 0;
}
bool edge[N][N];
int s1[N], s0[N];
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, seed;
cin >> n >> seed;
srand(seed);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (read()) // ij 黑边
++s1[i], ++s1[j];
else // ij 白边
++s0[i], ++s0[j];
ll ans = 0;
for (int i = 0; i < n; ++i) ans += s1[i] * s0[i]; // 异色角数量
cout << (ll)n * (n - 1) * (n - 2) / 6 - ans / 2 << '\n';
return 0;
} 
投递字节跳动等公司6个岗位 >
查看7道真题和解析