A：honoka和格点三角形
思路：由于三角形面积为2，而且保证三角形的一边与x轴或y轴平行，从而可以推出与某轴平行的边长度要么是1要么是2.
1.考虑满足题意的三角形中与x轴平行：
- 与x轴平行的边长为2，对答案的贡献：m * (m - 2) % mod * (n - 1) % mod * 2 % mod;
- 与x轴平行的边长为1，对答案的贡献：m * (m - 1) % mod * (n - 2) % mod * 2 % mod;
2.考虑满足题意的三角形中与y轴平行：
- 与y轴平行的边长为2，对答案的贡献(舍弃与x轴平行的三角形，不重复计数)：
(n - 2) * (n - 2) % mod * (m - 1) % mod * 2 % mod; - 与y轴平行的边长为1，对答案的贡献(舍弃与x轴平行的三角形，不重复计数)：
(n - 2) * (n - 1) % mod * (m - 2) % mod * 2 % mod;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll m, n;
ll solve1(ll n, ll m){
ll ans;
ans = m * (m - 2) % mod * (n - 1) % mod * 2 % mod;
return ans;
}
ll solve2(ll n, ll m){
ll ans;
ans = m * (m - 1) % mod * (n - 2) % mod * 2 % mod;
return ans;
}
ll solve3(ll n, ll m){
ll ans;
ans = (n - 2) * (n - 2) % mod * (m - 1) % mod * 2 % mod;
return ans;
}
ll solve4(ll n, ll m){
ll ans;
ans = (n - 2) * (n - 1) % mod * (m - 2) % mod * 2 % mod;
return ans;
}
int main(){
while(scanf("%lld%lld", &n, &m) != EOF){
ll ans = 0;
ans = solve1(n, m);
ans = (ans + solve2(n, m)) % mod;
ans = (ans + solve3(n, m)) % mod;
ans = (ans + solve4(n, m)) % mod;
printf("%lld\n", ans);
}
return 0;
}
B：kotori和bangdream
思路：由于每一个音符都是等价的，直接利用数学公式求出一个音符的期望值
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
ll n, a, b, x;
int main(){
while(scanf("%lld%lld%lld%lld", &n, &x, &a, &b) != EOF){
ll up = a * x + b * (100 - x);
up *= n;
double ans = up / 100.0;
printf("%.2f\n", ans);
}
return 0;
}
C：umi和弓道
思路：这道题把题目简化，每一个点都不在坐标轴上。所以我们就可以直接暴力弄，对于与umi在同一象限的，我们就直接忽略（因为你只能把板放在坐标轴上，所以肯定会把在同一象限的打掉）。不在同一象限的点，我们求出umi与它组成的线段与x轴或y轴的交点。与x轴的交点放在桶A，与y轴的交点放在桶B。然后按大小排序后，直接找枚举区间长度为n - k的答案，然后最后取min。具体细节，可以参考代码。
但是我这个代码，处理两个点表示的线段与x或y轴有无交点地方，写得很啰嗦。
处理交点，可以利用此方法 umi(x0, y0) A(x1, y1) if(x0 * x1 < 0) x轴有交点 if(y0 * y1 < 0) y轴有交点
下面大篇幅代码，可以用上面思路简化。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 5;
ll x, y;
int n, k;
vector<double>Y;
vector<double>X;
double Get_Y(ll x0, ll y0, ll x1, ll y1){
if(x0 == x1) return y0 * 1.0;
return (y1 * x0 - x1 * y0) / (1.0 * (x0 - x1));
}
double Get_X(ll x0, ll y0, ll x1, ll y1){
//printf("x1 = %lld y1 = %lld\n", x1, y1);
if(y0 == y1) return x0;
return (x1 * y0 - x0 * y1) / (1.0 * (y0 - y1));
}
int check(ll x, ll y){
if(x > 0 && y > 0) return 1;
if(x > 0 && y < 0) return 4;
if(x < 0 && y > 0) return 2;
if(x < 0 && y < 0) return 3;
}
void print(){
int Size = X.size();
for(int i = 0; i < Size; i++){
printf("X[%d] = %f\n", i + 1, X[i]);
}
Size = Y.size();
for(int i = 0; i < Size; i++){
printf("Y[%d] = %f\n", i + 1, Y[i]);
}
}
int main(){
while(scanf("%lld%lld%d%d", &x, &y, &n, &k) != EOF){
Y.clear(); X.clear();
int res = n - k;
ll f, s;
int opt = check(x, y);
for(int i = 1; i <= n; i++){
scanf("%lld%lld", &f, &s);
int tmp = check(f, s);
if(opt == tmp) continue;
if(opt == 1){
if(tmp == 2){
double y1 = Get_Y(x, y, f, s);
Y.push_back(y1);
}
else if(tmp == 3){
double y1 = Get_Y(x, y, f, s);
Y.push_back(y1);
double x1 = Get_X(x, y, f, s);
X.push_back(x1);
}
else{
double x1 = Get_X(x, y, f, s);
X.push_back(x1);
}
}
if(opt == 2){
if(tmp == 1){
double y1 = Get_Y(x, y, f, s);
Y.push_back(y1);
}
else if(tmp == 3){
double x1 = Get_X(x, y, f, s);
X.push_back(x1);
}
else{
double y1 = Get_Y(x, y, f, s);
Y.push_back(y1);
double x1 = Get_X(x, y, f, s);
X.push_back(x1);
}
}
if(opt == 3){
if(tmp == 1){
double y1 = Get_Y(x, y, f, s);
Y.push_back(y1);
double x1 = Get_X(x, y, f, s);
X.push_back(x1);
}
else if(tmp == 2){
double x1 = Get_X(x, y, f, s);
X.push_back(x1);
}
else{
double y1 = Get_Y(x, y, f, s);
Y.push_back(y1);
}
}
if(opt == 4){
if(tmp == 1){
double x1 = Get_X(x, y, f, s);
X.push_back(x1);
}
else if(tmp == 2){
double y1 = Get_Y(x, y, f, s);
Y.push_back(y1);
double x1 = Get_X(x, y, f, s);
X.push_back(x1);
}
else{
double y1 = Get_Y(x, y, f, s);
Y.push_back(y1);
}
}
}
sort(X.begin(), X.end());
sort(Y.begin(), Y.end());
int Size = X.size();
double ans = 1e15;
for(int i = 0; i + res - 1 < Size; i++){
int j = i + res - 1;
ans = min(ans, X[j] - X[i]);
}
Size = Y.size();
for(int i = 0; i + res - 1 < Size; i++){
int j = i + res - 1;
ans = min(ans, Y[j] - Y[i]);
}
//print();
if(ans == 1e15) printf("-1\n");
else printf("%.8f\n", ans);
}
return 0;
}
D：hanayo和米饭
思路：直接暴力枚举1-n谁没出现即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n;
bool vis[maxn];
int main(){
while(scanf("%d", &n) != EOF){
int val;
for(int i = 1; i < n; i++) scanf("%d", &val), vis[val] = true;
for(int i = 1; i <= n; i++){
if(!vis[i]) printf("%d\n", i);
}
}
return 0;
}
E：rin和快速迭代
思路：f(x)表示x的因数个数 设x的质因数为,质因数对应的指数为
,那么
感想：当时做这题的时候，我求质因数指数，算了一下大概复杂度是。可是，我在暴力跑1e12的时候，发现迭代次数好像挺小的，于是就暴力莽了一发，居然过了。但是数学证明我不太会，如果有会的，希望有人可以留言告诉我！
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
ll n;
ll Get(ll n){
ll ans = 1;
for(ll i = 2; i * i <= n; i++){
if(n % i == 0){
int num = 1;
while(n % i == 0){
num++;
n /= i;
}
ans *= num;
}
}
if(n > 1) ans *= 2;
return ans;
}
int main(){
while(scanf("%lld", &n) != EOF){
ll num = 0;
while(n != 2){
num++;
n = Get(n);
}
printf("%lld\n", num);
}
return 0;
}
F：maki和tree
思路：理解统计方法后，我们发现黑点是特殊点，可以枚举。怎么枚举呢？
枚举其中一个黑点A，怎么统计这个点对答案的贡献呢？
我们把这棵树除黑点A的其余黑点从树中拿掉，这下就变成很多棵树。黑点A所在的那棵树就发现贡献计算公式，这个就显然求出贡献值。如果不懂，可以看代码。
所以可以用并查集维护白点集合的大小，方便统计答案
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
ll siz[maxn];
int fa[maxn];
int n;
char s[maxn];
vector<int>pos[maxn];
int find_fa(int x){
if(x != fa[x]) return fa[x] = find_fa(fa[x]);
return x;
}
void join(int x, int y){
x = find_fa(x);
y = find_fa(y);
if(x == y) return ;
fa[x] = y;
siz[y] += siz[x];
}
int main(){
while(scanf("%d", &n) != EOF){
scanf("%s", s + 1);
int x, y;
for(int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1, pos[i].clear();
for(int i = 1; i < n; i++){
scanf("%d%d", &x, &y);
if(s[x] == 'W' && s[y] == 'W'){
join(x, y);
}
if(s[x] == 'W' && s[y] == 'B'){
pos[y].push_back(x);
}
if(s[x] == 'B' && s[y] == 'W'){
pos[x].push_back(y);
}
}
ll ans = 0;
for(int i = 1; i <= n; i++){
if(s[i] == 'B'){
ll sum = 0, sum_1 = 0;
int Size = pos[i].size();
for(int j = 0; j < Size; j++){
sum += siz[find_fa(pos[i][j])];
}
ans += sum;
for(int j = 0; j < Size; j++){
ll num = siz[find_fa(pos[i][j])];
sum_1 += num * (sum - num);
}
ans += sum_1 / 2;
}
}
printf("%lld\n", ans);
}
return 0;
}
G：eli和字符串
思路：开26个桶记录位置，然后固定长度更新答案
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int n, k;
vector<int>pos[30];
char s[maxn];
int main(){
while(scanf("%d%d", &n, &k) != EOF){
scanf("%s", s + 1);
for(int i = 1; i <= n; i++){
int in = s[i] - 'a' + 1;
pos[in].push_back(i);
}
int ans = maxn;
for(int i = 1; i <= 26; i++){
int Size = pos[i].size();
if(Size < k) continue;
for(int j = 0; j + k - 1 < Size; j++){
int r = j + k - 1;
ans = min(ans, pos[i][r] - pos[i][j] + 1);
}
}
if(ans == maxn) printf("-1\n");
else printf("%d\n", ans);
}
return 0;
}
H：nozomi和字符串
思路：求最大值，发现具有二分性，所以利用左闭右开区间。
check函数如何写呢？
对于二分的一个答案len，以此固定长度枚举区间，判断是否把01区间转化为全0或全1，利用前缀和即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int pre[maxn];
char s[maxn];
int n, k;
bool check(int len){
for(int i = 1; i + len - 1 <= n; i++){
int j = i + len - 1;
int sum = pre[j] - pre[i - 1];
if(min(len - sum, sum) <= k) return true;
}
return false;
}
void print(){
for(int i = 1; i <= n; i++){
printf("pre[%d] = %d\n", i, pre[i]);
}
}
int main(){
while(scanf("%d%d", &n, &k) != EOF){
scanf("%s", s + 1);
for(int i = 1; i <= n; i++){
int val = s[i] - '0';
pre[i] = pre[i - 1] + val;
}
//print();
int l, r;
l = 1, r = n + 1;
while(r - l > 1){
int mid = (l + r) / 2;
if(check(mid)){
l = mid;
}
else{
r = mid;
}
}
printf("%d\n", l);
}
return 0;
}
I:nico和niconiconi
思路：简单dp,dp[i]表示从开头到第i个字符获得的最大分数
更新3种方式
dp[i] = max(dp[i], dp[i - 4] + a);
dp[i] = max(dp[i], dp[i - 6] + b);
dp[i] = max(dp[i], dp[i - 10] + c);
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 5;
ll dp[maxn];
string s1 = "nico", s2 = "niconi", s3 = "niconiconi";
ll a, b, c, n;
char s[maxn];
bool check(int l, int r, int opt){
if(l <= 0) return false;
if(opt == 1){
int Size = s1.size();
for(int i = 0; i < Size; i++){
if(s[i + l] != s1[i]) return false;
}
}
if(opt == 2){
int Size = s2.size();
for(int i = 0; i < Size; i++){
if(s[i + l] != s2[i]) return false;
}
}
if(opt == 3){
int Size = s3.size();
for(int i = 0; i < Size; i++){
if(s[i + l] != s3[i]) return false;
}
}
return true;
}
int main(){
while(scanf("%lld%lld%lld%lld", &n, &a, &b, &c) != EOF){
scanf("%s", s + 1);
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++){
dp[i] = dp[i - 1];
if(check(i - 3, i, 1)){
dp[i] = max(dp[i], dp[i - 4] + a);
}
if(check(i - 5, i, 2)){
dp[i] = max(dp[i], dp[i - 6] + b);
}
if(check(i - 9, i, 3)){
dp[i] = max(dp[i], dp[i - 10] + c);
}
}
printf("%lld\n", dp[n]);
}
return 0;
}
J:u's的影响力
思路：乘法可以联想指数加法，然后写几个例子，发现指数呈现斐波拉契变化。
注意几个坑点：由于x,y,a很大，所以我们要先取模，防止利用快速幂时爆long long
利用欧拉降幂条件 1
，所以坑点就是要判断a与p是否互质
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct mat{
int r, c;
ll a[5][5];
mat(){
memset(a, 0, sizeof(a));
}
};
mat mul(mat A, mat B, ll mod){
mat C;
C.r = A.r; C.c = B.c;
for(int i = 1; i <= C.r; i++){
for(int j = 1; j <= C.c; j++){
for(int k = 1; k <= A.c; k++){
C.a[i][j] += A.a[i][k] * B.a[k][j] % mod;
C.a[i][j] %= mod;
}
}
}
return C;
}
mat power(mat A, ll b, ll mod){
mat res;
res.c = res.r = A.r;
for(int i = 1; i <= res.r; i++) res.a[i][i] = 1;
while(b){
if(b & 1) res = mul(res, A, mod);
b >>= 1;
A = mul(A, A, mod);
}
return res;
}
ll quick_mod(ll a, ll b, ll mod){
ll sum = 1;
while(b){
if(b & 1) sum = sum * a % mod;
a = a * a % mod;
b /= 2;
}
return sum;
}
int main(){
ll m = 1e9 + 7, ans = 1;
ll n, x, y, a, b;
cin >> n >> x >> y >> a >> b;
if(n == 1) {cout << x % m << endl; return 0;}
if(n == 2) {cout << y % m << endl; return 0;}
if(x % m == 0 || y % m == 0 || a % m == 0) {cout << 0 << endl; return 0;}
x %= m;
y %= m;
a = quick_mod(a % m, b, m); ///这里要注意a对m取模
mat a_; a_.r = a_.c = 2; a_.a[1][1] = a_.a[1][2] = a_.a[2][1] = 1;
mat opt1, opt2;
opt1.r = opt2.r = 2; opt1.c = opt2.c = 1;
opt1.a[1][1] = 0; opt1.a[2][1] = 1;
opt2.a[1][1] = 1; opt2.a[2][1] = 0;
a_ = power(a_, n - 2, m - 1);
mat c = mul(a_, opt1, m - 1);
//printf("x = %lld\n", c.a[1][1]);
ans = ans * quick_mod(x, c.a[1][1], m) % m;
c = mul(a_, opt2, m - 1);
//printf("y = %lld\n", c.a[1][1]);
ans = ans * quick_mod(y, c.a[1][1], m) % m;
///
mat d; d.r = d.c = 3; d.a[1][1] = d.a[1][2] = d.a[1][3] = d.a[2][1] = d.a[3][3] = 1;
mat opt3; opt3.r = 3; opt3.c = 1; opt3.a[1][1] = opt3.a[2][1] = 0; opt3.a[3][1] = 1;
d = power(d, n - 2, m - 1);
c = mul(d, opt3, m - 1);
//printf("a = %lld\n", c.a[1][1]);
ans = ans * quick_mod(a, c.a[1][1], m) % m;
printf("%lld\n", ans);
return 0;
}
京公网安备 11010502036488号