A 2025年新年农场计划
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define N 10005
#define inf 0x3f3f3f3f-1
int tot;
int d[N];
int cnt=1;
int dis[N];
int head[N];
int n,m,s,t;
struct Edge{
int to,nxt,flow;
}edge[4400000];
void add(int x,int y,int z){
edge[++cnt].to=y;
edge[cnt].nxt=head[x];
edge[cnt].flow=z;
head[x]=cnt;
}
bool bfs(){
memset(d,0,sizeof d); d[s]=1;
std::queue<int> q; q.push(s);
while(q.size()){
int u=q.front();q.pop();
for(int i=head[u];i;i=edge[i].nxt){
int to=edge[i].to;
if(!edge[i].flow) continue;
if(d[to]) continue;
d[to]=d[u]+1;
q.push(to);
if(to==t) return 1;
}
}
return 0;
}
int dinic(int now,int flow){
if(now==t) return flow;
int rest=flow;
for(int i=head[now];i;i=edge[i].nxt){
if(!rest) return flow;
int to=edge[i].to;
if(!edge[i].flow) continue;
if(d[to]!=d[now]+1) continue;
int k=dinic(to,std::min(rest,edge[i].flow));
if(!k) d[to]=0;
rest-=k;
edge[i].flow-=k;
edge[i^1].flow+=k;
}
return flow-rest;
}
signed main(){
scanf("%d",&n); s=n+1; t=s+1;
for(int x,i=1;i<=n;i++) scanf("%d",&x),tot+=x,add(s,i,x),add(i,s,0);
for(int x,i=1;i<=n;i++) scanf("%d",&x),tot+=x,add(i,t,x),add(t,i,0);
scanf("%d",&m);
for(int i=1;i<=m;i++){
int T,tota,totb;
scanf("%d%d%d",&T,&tota,&totb);
tot+=tota+totb;
add(s,n+2+i,tota); add(n+2+i,s,0);
add(n+2+i+m,t,totb); add(t,n+2+i+m,0);
for(int x,j=1;j<=T;j++){
scanf("%d",&x);
add(n+2+i,x,inf);
add(x,n+2+i,0);
add(x,n+2+i+m,inf);
add(n+2+i+m,x,0);
}
}
int maxflow=0,flow=0;
while(bfs())
while(flow=dinic(s,0x3f3f3f3f)) maxflow+=flow;
printf("%d\n",tot-maxflow);
return 0;
}
B 上次铺瓷砖这次装小路？？
这是一个典型的动态规划问题，类似于完全背包问题。定义 dp[j] 为覆盖 j 米所需的最小费用。初始时，dp[0] = 0（覆盖 0 米不需要费用），其余初始化为无穷大。对于每个长度 j，遍历所有可能的彩灯长度 i（1 到 n），若 j >= i，则更新状态：
dp[j] = min(dp[j], dp[j-i] + sum[i])。
最终答案即为 dp[m]。
#include <bits/stdc++.h>
using namespace std;
int main() {
int m, n;
cin >> m >> n;
vector<int> sum(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> sum[i];
}
vector<int> dp(m + 1, INT_MAX);
dp[0] = 0;
for (int j = 1; j <= m; ++j) {
for (int i = 1; i <= n; ++i) {
if (i <= j && dp[j - i] != INT_MAX) {
dp[j] = min(dp[j], dp[j - i] + sum[i]);
}
}
}
cout << (dp[m] == INT_MAX ? -1 : dp[m]) << endl;
return 0;
}
C 乘法逆元
逆元基础
#include <bits/stdc++.h>
using namespace std;
int n, p, inv[3000005];
void write(int x) {
if (x > 9) write(x / 10);
putchar(x % 10 ^ 48);
}
int main() {
cin >> n >> p;
inv[1] = 1;
for (int i = 2; i <= n; i++) inv[i] = 1ll * (p - p / i) * inv[p % i] % p;
for (int i = 1; i <= n; i++) write(inv[i]), putchar(10);
}
D ZL的零食
操作1 的话就区间维护最小值，这个最小值是为了操作2的输出
然后再维护一个标记，表示这个区间要最小变成x，所以这个标记要取最大值
操作2就维护一个堆，类似NOI2005超级钢琴的堆
在给定区间[ l , r ] 内先查一个最小值，设这个最小值的位置为p
那么我们还需要查询[ 1 , p - 1 ]和[ p + 1 , r ]内的最小值
这样找到所要求的x 个最小值就可以了
用一个优先队列实现，只要够了x个元素就可以break
因为先出来的元素一定比后出来的元素小
所以线段树还需要维护区间最小值的位置
#include <bits/stdc++.h>
#define A 2000010
using namespace std;
typedef long long ll;
struct node {
int l, r, w, f, p;
friend bool operator < (const node a, const node b) {
return a.w > b.w;
}
}tree[A];
void up(int k) {
tree[k].w = INT_MAX;
if (tree[k << 1].w < tree[k].w) tree[k].w = tree[k << 1].w, tree[k].p = tree[k << 1].p;
if (tree[k << 1 | 1].w < tree[k].w) tree[k].w = tree[k << 1 | 1].w, tree[k].p = tree[k << 1 | 1].p;
}
int n, w[A], m, opt, a, b, k, x, sta[A], top;
priority_queue<node> q;
void build(int k, int l, int r) {
tree[k].l = l; tree[k].r = r;
if (l == r) {tree[k].w = w[l]; tree[k].p = l; return;}
int m = (l + r) >> 1;
build(k << 1, l, m);
build(k << 1 | 1, m + 1, r);
up(k);
}
void down(int k) {
tree[k << 1].f = max(tree[k << 1].f, tree[k].f);
tree[k << 1 | 1].f = max(tree[k << 1 | 1].f, tree[k].f);
tree[k << 1].w = max(tree[k << 1].w, tree[k].f);
tree[k << 1 | 1].w = max(tree[k << 1 | 1].w, tree[k].f);
tree[k].f = 0;
}
void change(int k, int l, int r, int val) {
if (tree[k].l >= l and tree[k].r <= r) {
tree[k].w = max(tree[k].w, val);
tree[k].f = max(tree[k].f, val);
return;
}
if (tree[k].f) down(k);
int m = (tree[k].l + tree[k].r) >> 1;
if (l <= m) change(k << 1, l, r, val);
if (r > m) change(k << 1 | 1, l, r, val);
up(k);
}
pair<int, int> ask(int k, int l, int r) {
if (tree[k].l >= l and tree[k].r <= r) return make_pair(tree[k].w, tree[k].p);
if (tree[k].f) down(k);
int m = (tree[k].l + tree[k].r) >> 1; pair<int, int> ans = make_pair(INT_MAX, 0);
if (l <= m) {
pair<int, int> p = ask(k << 1, l, r);
if (p.first < ans.first) ans = p;
}
if (r > m) {
pair<int, int> p = ask(k << 1 | 1, l, r);
if (p.first < ans.first) ans = p;
}
return ans;
}
int main(int argc, char const *argv[]) {
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
build(1, 1, n); cin >> m;
while (m--) {
scanf("%d%d%d%d", &opt, &a, &b, &k);
if (opt == 1) change(1, a, b, k);
else {
scanf("%d", &x); top = 0;
while (!q.empty()) q.pop();
pair<int, int> p = ask(1, a, b);
q.push(node{a, b, p.first, 0, p.second});
while (!q.empty()) {
node fr = q.top(); q.pop();
if (fr.w >= k) continue;
sta[++top] = fr.w;
pair<int, int> p1 = ask(1, fr.l, fr.p - 1), p2 = ask(1, fr.p + 1, fr.r);
q.push(node{fr.l, fr.p - 1, p1.first, 0, p1.second});
q.push(node{fr.p + 1, fr.r, p2.first, 0, p2.second});
if (top == x) break;
}
if (top != x) puts("-1");
else {
sort(sta + 1, sta + top + 1);
for (int i = 1; i <= top; i++) printf("%d ", sta[i]); puts("");
}
}
}
return 0;
}
E 2025新年祝福语生成器
def calculate_min_heartvalue(s: str, t: str) -> int:
if len(s) != len(t):
return -1
n = len(s)
heart_value = 0
# 检查每个位置
for i in range(n):
if s[i] != t[i]:
# 如果字符不同且都是字母，需要使用通配符
if s[i].isalpha() and t[i].isalpha():
heart_value += 1 # 替换为'*'的成本
else:
# 如果包含数字且不同，无法转换
return -1
return heart_value
# 读取输入
s = input().strip()
t = input().strip()
# 计算并输出结果
result = calculate_min_heartvalue(s, t)
print(result)
F 小露似乎很喜欢7
签到题
n = int(input())
summ = 0
a = input().split()
for i in a:
if '7' in i:
ii = int(i)
summ += ii
else:
ii = int(i)
if ii % 7 == 0:
summ += ii
print(summ)
京公网安备 11010502036488号