写福字
对时间进行二分：在当前时间里能完成，右端减少；不能完成，左端减少。注意：m可以为0.
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
// 检查在给定时间内是否能完成所需数量的福字
bool check(ll time, ll m, int n, vector<int>& a, vector<int>& b) {
ll total = 0; // 在给定时间内能写的福字总数
for(int i = 0; i < n; i++) {
// 计算第i个人在给定时间内能写多少福字
// 注意防止溢出，先除后乘
total += (time / a[i]) * b[i];
if(total >= m) return true; // 如果已经达到目标，提前返回
}
return total >= m;
}
int main() {
ll m; // 需要完成的福字数量
int n; // 参与人数
cin >> m >> n;
vector<int> a(n), b(n); // a存储每人写一幅所需时间，b存储每人能写的数量
for(int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
}
// 二分查找时间
ll left = 0, right = 1e18; // 时间范围
ll ans = right;
while(left <= right) {
ll mid = left + (right - left) / 2;
if(check(mid, m, n, a, b)) {
ans = mid;
right = mid - 1; // 尝试更小的时间
} else {
left = mid + 1; // 需要更多时间
}
}
cout << ans << endl;
return 0;
}
贴福字
先不考虑重叠，能放下放下，然后再考虑重叠变成两倍。
#include <iostream>
using namespace std;
int main() {
int a;
cin>>a;
cout<<2*(a/2)*(a/2);
}
// 64 位输出请用 printf("%lld")
抢红包
线段树，算区间和
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
struct Node {
ll sum; // 区间和
ll lazy; // 懒标记
} tree[MAXN * 4]; // 开4倍空间确保足够
int n, m;
ll a[MAXN];
// 向上更新节点信息
void pushUp(int node) {
tree[node].sum = tree[node * 2].sum + tree[node * 2 + 1].sum;
}
// 下推懒标记
void pushDown(int node, int l, int r) {
if (tree[node].lazy != 0) {
int mid = (l + r) >> 1;
// 更新左子节点
tree[node * 2].lazy += tree[node].lazy;
tree[node * 2].sum += tree[node].lazy * (mid - l + 1);
// 更新右子节点
tree[node * 2 + 1].lazy += tree[node].lazy;
tree[node * 2 + 1].sum += tree[node].lazy * (r - mid);
// 清除当前节点的懒标记
tree[node].lazy = 0;
}
}
// 建树
void build(int node, int l, int r) {
tree[node].lazy = 0;
if (l == r) {
tree[node].sum = a[l];
return;
}
int mid = (l + r) >> 1;
build(node * 2, l, mid);
build(node * 2 + 1, mid + 1, r);
pushUp(node);
}
// 区间修改
void update(int node, int l, int r, int L, int R, ll val) {
if (L <= l && r <= R) {
tree[node].lazy += val;
tree[node].sum += val * (r - l + 1);
return;
}
pushDown(node, l, r);
int mid = (l + r) >> 1;
if (L <= mid) update(node * 2, l, mid, L, R, val);
if (R > mid) update(node * 2 + 1, mid + 1, r, L, R, val);
pushUp(node);
}
// 区间查询
ll query(int node, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return tree[node].sum;
}
pushDown(node, l, r);
int mid = (l + r) >> 1;
ll res = 0;
if (L <= mid) res += query(node * 2, l, mid, L, R);
if (R > mid) res += query(node * 2 + 1, mid + 1, r, L, R);
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build(1, 1, n);
while (m--) {
int type;
cin >> type;
if (type == 1) {
int x, s, t, p;
cin >> x >> s >> t >> p;
// 计算每人分得的金额，使用long long避免溢出
ll val = s / p;
// 发红包的人扣钱
update(1, 1, n, x, x, -s);
// 收红包的人加钱
if (val > 0) { // 只有在有钱可分的情况下才更新
update(1, 1, n, t, t + p - 1, val);
}
} else {
int l, r;
cin >> l >> r;
cout << query(1, 1, n, l, r) << "\n";
}
}
return 0;
}
CCL的作业
首先，对模数 n 进行质因数分解。这是因为对于不同的质因数，我们可以分别考虑它们在模 n 意义下的影响，最后利用中国剩余定理（CRT）组合这些影响。但在这个问题中，我们实际上并不需要显式地使用 CRT，因为每个质因数对应的解集在合并时，只需要考虑它们数量的乘积（基于一些数论原理，特别是当模数是互质的质数的幂的乘积时）。
欧拉函数的应用：
对于模数 n 的每个质因数 p^b（其中 p 是质数，b 是正整数），我们需要考虑 x^p≡y(modp^b)（其中 y 是某个整数）在模 p^b 意义下有多少不同的解。这可以通过欧拉函数 ϕ(p^b) 来减少可能的解的数量，因为 x^p 在模 p^b 下的取值范围实际上受限于 ϕ(p^b)（当 p不等于2 或 b≤2 时，ϕ(p^b)=（p^（b−1））*(p−1)；当 p=2 且 b>2 时，ϕ(2^b)=2^(b−1)）。注：“之写的b-2是打字打错了，题没有问题”
递归处理大幂次：
当 b>a 时（即模数的幂次大于指数），我们需要递归地处理一个更小的模数问题。这是因为 x^p 在模 p^b 下的取值可能受到 x 在模 p^(b−a)（或更小的幂次）下的取值的影响。
特殊情况处理：
当 p=2 且 b>2 时，如果 a 是奇数，解的数量需要乘以 2，因为 x 和 −x 在模 2^b 下是两个不同的解（但在模 2^(b−1) 下是相同的）。
当 b≤a 时，需要额外考虑 x=0 作为一个解的情况（因为 0^p=0 对所有 p 都成立）。
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,a;
int gcd(int k1,int k2){
if (k2==0)
return k1;
return gcd(k2,k1%k2);
}
int solve(int p,int b,int mo){
int phi=mo/p*(p-1);
if (p==2&&b>2) phi=mo/4;
int ans=phi/gcd(phi,a);
if (p==2&&b>2&&a%2)
ans*=2;
if (b<=a)
ans++;
else {
for (int i=1;i<=a;i++)
mo/=p;
ans+=solve(p,b-a,mo);
}
return ans;
}
int main(){
scanf("%d%d%d",&a,&m,&n);
int ans=1;
for (int i=2;1ll*i*i<=n;i++)
if (n%i==0){
int k1=0,k2=1;
while (n%i==0){
n/=i;
k1++;
k2*=i;
}
ans=ans*solve(i,k1,k2);
}
if (n>1)
ans=ans*solve(n,1,n);
cout<<ans<<endl;
return 0;
}
铺瓷砖咯
使用动态规划来解决此问题。定义状态 dp[i][c][k]，表示处理到第 i 个位置时，颜色为 c，且该颜色已连续出现 k 次（k 为 1 或 2）的方案数。状态转移分为两种情况：
1. 前一个颜色相同且连续次数为 1：当前颜色可以继续相同，连续次数变为 2。
2. 前一个颜色不同：当前颜色只能连续出现 1 次。
由于每次状态仅依赖于前一次的状态，因此可以优化空间复杂度，只保留前一次的状态。
MOD = 10**9 + 7
n = int(input())
if n == 0:
print(0)
elif n == 1:
print(3)
else:
# 初始状态：第一个瓷砖的k=1，每个颜色各有1种方案
prev_k1 = [1, 1, 1] # 颜色R, G, B的k=1方案数
prev_k2 = [0, 0, 0] # 颜色R, G, B的k=2方案数
for _ in range(2, n + 1):
curr_k1 = [0] * 3
curr_k2 = [0] * 3
for c_prev in range(3):
# 处理k_prev=1的情况
# 相同颜色转移到k=2
curr_k2[c_prev] = (curr_k2[c_prev] + prev_k1[c_prev]) % MOD
# 不同颜色转移到k=1
for c_new in range(3):
if c_new != c_prev:
curr_k1[c_new] = (curr_k1[c_new] + prev_k1[c_prev]) % MOD
# 处理k_prev=2的情况
# 必须不同颜色，转移到k=1
for c_new in range(3):
if c_new != c_prev:
curr_k1[c_new] = (curr_k1[c_new] + prev_k2[c_prev]) % MOD
prev_k1, prev_k2 = curr_k1, curr_k2
total = (sum(prev_k1) + sum(prev_k2)) % MOD
print(total)
双色城市连接
Kruskal算法
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
def solve():
# 读取输入
n, x, y = map(int, input().split())
colors = list(map(int, input().split()))
# 构建所有可能的边
edges = []
for i in range(n):
for j in range(i+1, n):
# 根据颜色确定边的权重
weight = x if colors[i] == colors[j] else y
edges.append((weight, i, j))
# 按权重排序
edges.sort()
# Kruskal算法
uf = UnionFind(n)
total_cost = 0
edges_used = 0
for weight, u, v in edges:
if uf.union(u, v):
total_cost += weight
edges_used += 1
if edges_used == n-1:
break
return total_cost
if __name__ == "__main__":
print(solve())
比赛中的最短代码
a,b,c=map(int,input().split())
if c<=b:
print((a-1)*c)
exit()
c1=[0,0]
for i in map(int,input().split()):
c1[i]+=1
print(b*a) if 0 in c1 else print(b*(a-2)+c)
京公网安备 11010502036488号