C Tokitsukaze and a+b=n (hard)

思路：

差分 + 算贡献
每个位置被几条线段覆盖，直接返回c[i] * c[n - i] - o(i == j)的情况即可，其中所有的位置的相同的线段可以利用该题的medium难度的结论预处理出，res - s即为最终答案。

代码如下：

// Time:	2023-01-19 21:19:40
// Problem: Tokitsukaze and a+b=n (hard)
// Contest: NowCoder
// URL: 	https://ac.nowcoder.com/acm/contest/46810/C
// Memory Limit: 	524288 MB
// Time Limit: 		4000 ms#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include #define fast ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)#define mkpr make_pair
#define endl '\n'
#define x first
#define y second
#define y1 Y1
// #define int long longusing namespace std;typedef long long LL;
typedef pair PII;const int mod = 998244353;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;const int N = 4e5 + 10, M = 2e5 + 10;LL gcd(LL a,LL b){return b ? gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}int T = 1, cases = 1;
int n, m, times;int s;
int diff[N];void solve()
{scanf("%d%d", &n, &m);for (int i = 1; i <= m; i ++ ){int l, r;scanf("%d%d", &l, &r);diff[l] += 1;diff[r + 1] -= 1;s = ((LL)s + max(min(r, n - l) - max(l, n - r) + 1, 0)) % mod;}for (int i = 1; i <= n; i ++ )diff[i] += diff[i - 1];int res = 0;for (int i = 1; i <= n; i ++ )res = ((LL)res + (LL)diff[i] * diff[n - i]) % mod;printf("%d\n", ((LL)res - s + mod) % mod);return;
}signed main()
{//fast;//cin >> T;// scanf("%d", &T);while(T -- )solve();return 0;
}

E Tokitsukaze and Function

思路：

基本不等式（对勾函数） + 二分

代码如下：

// Time:	2023-01-20 12:19:38
// Problem: Tokitsukaze and Function
// Contest: NowCoder
// URL: 	https://ac.nowcoder.com/acm/contest/46810/E
// Memory Limit: 	524288 MB
// Time Limit: 		4000 ms#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include #define fast ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)#define mkpr make_pair
#define endl '\n'
#define x first
#define y second
#define y1 Y1
// #define int long longusing namespace std;typedef long long LL;
typedef pair PII;const int mod = 998244353;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;const int N = 2e5 + 10, M = N * 2;LL gcd(LL a,LL b){return b ? gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}int T = 1, cases = 1;
// int n, m, times;
LL n;LL f(LL x)
{if (x == 0) return 5e18;return n / x + x - 1;
}void solve()
{LL l1, r1;scanf("%lld%lld%lld", &n, &l1, &r1);LL t = (LL)sqrt(n);while (t * t < n) t ++ ;if (t < r1 && f(t) > f(t + 1)){cout << t + 1 << endl;return;}t = min(t, r1);LL l = l1, r = t;while (l < r){LL mid = l + r >> 1;if (f(mid) == f(t)) r = mid;else l = mid + 1;}cout << l << endl;return;
}signed main()
{//fast;//cin >> T;scanf("%d", &T);while(T -- )solve();return 0;
}

F Tokitsukaze and Gold Coins (easy)

思路：

两次dfs

代码如下：

// Time:	2023-01-19 20:47:36
// Problem: Tokitsukaze and Gold Coins (easy)
// Contest: NowCoder
// URL: 	https://ac.nowcoder.com/acm/contest/46810/F
// Memory Limit: 	524288 MB
// Time Limit: 		6000 ms#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include #define fast ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)#define mkpr make_pair
#define endl '\n'
#define x first
#define y second
#define y1 Y1
// #define int long longusing namespace std;typedef long long LL;
typedef pair PII;const int mod = 998244353;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;const int N = 5e5 + 10, M = N * 2;LL gcd(LL a,LL b){return b ? gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}int T = 1, cases = 1;
int n, m, times;int g[N][4];
bool m1[N][4], m2[N][4];int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};void dfs(int x, int y, int f)
{if (f == 0) m1[x][y] = true;else m2[x][y] = true;for (int i = 0; i < 4; i ++ ){if (f == 0 && (i == 0 || i == 3) || f && (i == 1 || i == 2)) continue;int a = x + dx[i], b = y + dy[i];if (a < 1 || a > n || b < 0 || b > 3 || g[a][b]) continue;if (f == 0 && m1[a][b]) continue;if (f == 1 && m2[a][b]) continue;dfs(a, b, f);}
}void solve()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= 3; j ++ )g[i][j] = m1[i][j] = m2[i][j] = 0;while (m -- ){int x, y;scanf("%d%d", &x, &y);g[x][y] ^= 1;}dfs(1, 1, 0);dfs(n, 3, 1);int res = 0;for (int i = 1; i <= n; i ++ )for (int j = 1; j <= 3; j ++ ){if (i == 1 && j == 1) continue;if (m1[i][j] && m2[i][j])res ++ ;}cout << res << endl;return;
}signed main()
{//fast;//cin >> T;scanf("%d", &T);while(T -- )solve();return 0;
}

H Tokitsukaze and K-Sequence

思路：

单独算贡献

注：也可用两个数组算小于大于k的贡献

代码如下：

// Time:	2023-01-19 19:27:41
// Problem: Tokitsukaze and K-Sequence
// Contest: NowCoder
// URL: 	https://ac.nowcoder.com/acm/contest/46810/H
// Memory Limit: 	524288 MB
// Time Limit: 		4000 ms#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include #define fast ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)#define mkpr make_pair
#define endl '\n'
#define x first
#define y second
#define y1 Y1
// #define int long longusing namespace std;typedef long long LL;
typedef pair PII;const int mod = 998244353;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;const int N = 1e5 + 10, M = N * 2;LL gcd(LL a,LL b){return b ? gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}int T = 1, cases = 1;
int n, m, times;void solve()
{cin >> n;map mp, cnt;for (int i = 1; i <= n; i ++ ){int x;cin >> x;mp[x] ++ ;}// 极限只有100项for (auto it : mp)cnt[it.y] ++;int res[N] = {0};// 看似两重循环，其实时间复杂度最多才1e7for (int i = 1; i <= n; i ++ ){for (auto it : cnt)if (it.x <= i) res[i] += it.x * it.y;else res[i] += (i - 1) * it.y;}for (int i = 1; i <= n; i ++ )cout << res[i] << endl;return;
}signed main()
{fast;cin >> T;//scanf("%d", &T);while(T -- )solve();return 0;
}

L Tokitsukaze and Three Integers

思路：

预处理

代码如下：

// Time:	2023-01-19 19:22:51
// Problem: Tokitsukaze and Three Integers
// Contest: NowCoder
// URL: 	https://ac.nowcoder.com/acm/contest/46810/L
// Memory Limit: 	524288 MB
// Time Limit: 		4000 ms#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include #define fast ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)#define mkpr make_pair
#define endl '\n'
#define x first
#define y second
#define y1 Y1
// #define int long longusing namespace std;typedef long long LL;
typedef pair PII;const int mod = 998244353;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;const int N = 5010, M = N * 2;LL gcd(LL a,LL b){return b ? gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}int T = 1, cases = 1;
int n, m, times;LL a[N];
LL c[N];
LL d[N][N];void solve()
{int p;scanf("%d %d", &n, &p);for (int i = 1; i <= n; i ++ )scanf("%lld", &a[i]), a[i] %= p;for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ ){if (i == j) continue;int mult = a[i] * a[j] % p;c[mult] ++ ;d[i][mult] += 2;}for (int x = 0; x <= p - 1; x ++ ){LL res = 0;for (int k = 1; k <= n; k ++ ){int t = (x - a[k] + p) % p;res += c[t] - d[k][t];}cout << res << ' ';}cout << endl;return;
}signed main()
{// fast;//cin >> T;//scanf("%d", &T);while(T -- )solve();return 0;
}

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：PTA 1093 字符串A+B（C++实现）

下一篇：第二类换元法三角代换专项训练

2023牛客寒假算法基础集训营2

目录

C Tokitsukaze and a+b=n (hard)

E Tokitsukaze and Function

F Tokitsukaze and Gold Coins (easy)

H Tokitsukaze and K-Sequence

L Tokitsukaze and Three Integers

相关内容

热门资讯