怎么给别人做网站网站,天津网站建设美丽,erp软件免费版,如何网上建设网站文章目录 A - 三角形B - 好数组C - 前缀平方和序列D - 走一个大整数迷宫E - 前缀和前缀最大值 A - 三角形
map存一下每个数出现了多少次#xff0c;再遍历map
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pair再遍历map
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairint, char PIC;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;
typedef pairint, pairint, bool PIIB;const int N 1e5 10;
const int maxn 1e6 10;
const int mod 998244353;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;void solve()
{int n;cin n;mapint, int mp;for (int i 0; i n; i ){int x; cin x;mp[x] ;}for (auto t : mp){if (t.second 3){cout YES\n;return;}}cout NO\n;return;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;
// cin t;while (t--){solve();}
}B - 好数组
数组没有 0 就是好数组
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairint, char PIC;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;
typedef pairint, pairint, bool PIIB;const int N 1e5 10;
const int maxn 1e6 10;
const int mod 998244353;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;void solve()
{int n;cin n;vectorint a(n 1);for (int i 1; i n; i ) cin a[i];for (int i 1; i n; i ){if (a[i] 0){cout NO\n;return;}}cout YES\n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t--){solve();}
}C - 前缀平方和序列
对 x 开方得到的就是能存在数组里的所有数的个数我们要取 n 个也就是 C(sqrt(x), n)
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairint, char PIC;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;
typedef pairint, pairint, bool PIIB;const int N 1e5 10;
const int maxn 1e6 10;
const int mod 1e9 7;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;int Jc[maxn 1];void calJc() //求 maxn 以内的数的阶乘 不知道开多少就1e6吧爆不了
{Jc[0] Jc[1] 1;for(int i 2; i maxn; i) Jc[i] Jc[i - 1] * i % mod;
}int pow(int a, int n, int p) // 快速幂取模
{int ans 1;while (n){if (n 1) ans ans * a % p;a a * a % p;n 1;}return ans;
}int niYuan(int a, int b) //费马小定理求逆元
{return pow(a, b - 2, b);
}int C(int a, int b) // 组合数
{if(a b) return 0;return Jc[a] * niYuan(Jc[b], mod) % mod * niYuan(Jc[a - b], mod) % mod;
}void solve()
{calJc();int n, x;cin n x;int cnt sqrt(x);int ans C(cnt, n);cout ans \n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t--){solve();}
}D - 走一个大整数迷宫
首先需要注意到 c 的值和 b 一点关系都没有因为 b 不可能对 (p - 1) 有任何贡献
明确这一点之后只需要 bfs 就可以了注意需要判断 st[x][y][k] 不重复(x, y) 就是点坐标k 就是到达该点的余数
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairint, char PIC;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;
typedef pairint, pairint, bool PIIB;const int N 1e5 10;
const int maxn 1e6 10;
const int mod 1e9 7;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;int dx[4] {0, 0, 1, -1}, dy[4] {1, -1, 0, 0};struct node {int dist, res, x, y;
};void solve()
{int n, m, p;cin n m p;vectorvectorint a(n 1, vectorint(m 1)), b(n 1, vectorint(m 1));for (int i 1; i n; i )for (int j 1; j m; j )cin a[i][j];for (int i 1; i n; i )for (int j 1; j m; j )cin b[i][j];int ans INF;queuestruct node q;q.push({0, a[1][1] % (p - 1), 1, 1});vectorvectorvectorbool st(n 1, vectorvectorbool(m 1, vectorbool(p 1)));while (q.size()){auto t q.front();q.pop();if (st[t.x][t.y][t.res]) continue;st[t.x][t.y][t.res] true;if (t.x n t.y m t.res % (p - 1) 0){cout t.dist \n;return;}if (t.dist 1e6){cout -1 \n;return;}for (int i 0; i 4; i ){int nx t.x dx[i], ny t.y dy[i];if (nx 0 || nx n || ny 0 || ny m) continue;q.push({t.dist 1, (t.res a[nx][ny]) % (p - 1), nx, ny});}}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t--){solve();}
}E - 前缀和前缀最大值
a 的前缀最大值数量最多的情况就是把正数全都排在前面的时候此时数量为 正数个数1加的 1 代表最前面的前缀和 0
数量最少的情况就是把负数全都排在正数前面且正数从小到大排列这种情况怎么计算呢因为 b 的值域最大只有100所以用 cnt_pos[i][j] 表示前 i 个元素中 j 出现的次数之后计算最多需要多少个正数可以把负数都抵消即可
答案就是最大值-最小值1
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairint, char PIC;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;
typedef pairint, pairint, bool PIIB;const int N 10;
const int maxn 1e6 10;
const int mod 998244353;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;void solve()
{int n;cin n;vectorint a(n 1), pre_neg(n 1);vectorvectorint cnt_pos(n 1, vectorint(110));for (int i 1; i n; i ){cin a[i];pre_neg[i] pre_neg[i - 1] - min(a[i], (i64)0);for (int j 1; j 100; j ){cnt_pos[i][j] cnt_pos[i - 1][j] (a[i] j);}} int q;cin q;while (q -- ){int l, r;cin l r;int cnt_plus 0; // 正数个数for (int i 1; i 100; i ) cnt_plus cnt_pos[r][i] - cnt_pos[l - 1][i];int sum_tmp 0; // 当前正数之和int cnt_need 0; // 需要多少正数和负数抵消for (int i 1; i 100; i ){int cnt cnt_pos[r][i] - cnt_pos[l - 1][i];if (sum_tmp i * cnt (pre_neg[r] - pre_neg[l - 1])){cnt_need (pre_neg[r] - pre_neg[l - 1] - sum_tmp) / i;break;}else{cnt_need cnt;sum_tmp cnt * i;}}cout cnt_plus 1 - (cnt_plus - cnt_need 1) 1 \n;}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t--){solve();}
}
