技术标签: 代码菜鸡之CF刷题记录 图论
知识点:最短路
题目:无权简单图中加一条边避免起点 s s s 到终点 d d d 的最短路缩短,问合法方案数量。
思路:若在点 a , b a,b a,b 之间加一条边 g ′ g' g′ 可使最短路缩短,那更新的最短路一定是经过 g ′ g' g′ 边的。于是可以算出所有点到起点终点两点 s , d s,d s,d 的最短路( d i j k s t r a dijkstra dijkstra),遍历尝试添加所有可加边,检查是否是合法的(min(startdist[i], startdist[j]) + 1 + min(enddist[i], enddist[j])
)。
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define per(i, a, b) for(int i = a; i >= b; i--)
const int INF = 0x7fffffff;
#define ll long long
#define PII pair<int, int>
const int N =1e3 + 5;
using namespace std;
int n, s, d, m, k;
ll g[N][N], ans;
ll vis[N], startdist[N], enddist[N];
vector<PII> vec[N];
void init(){
memset(g, 0, sizeof(g));
rep(i, 1, n){
vec[i].clear();
startdist[i] = enddist[i] = INF;
}
}
void dijkstra(int s, ll dist[]){
memset(vis, 0, sizeof(vis));
priority_queue<PII, vector<PII>, greater<PII> > heap;
dist[s] = 0, heap.push({
0, s});
while(heap.size()){
PII now = heap.top(); heap.pop();
int nod = now.second;
if(vis[nod]) continue;
vis[nod] = 1;
for(auto j : vec[nod]){
int To = j.first, distmp = j.second;
if(dist[To] > now.first + distmp){
dist[To] = now.first + distmp;
heap.push({
dist[To], To});
}
}
}
return;
}
int main(){
cin >> n >> m >> s >> d;
init();
rep(i, 1, m){
int u, v; cin >> u >> v;
g[u][v] = g[v][u] = 1;
vec[u].push_back({
v, 1}), vec[v].push_back({
u, 1});
}
dijkstra(s, startdist);
dijkstra(d, enddist);
ans = 0;
rep(i, 1, n) rep(j, i + 1, n){
if(g[i][j]) continue;
if(min(startdist[i], startdist[j]) + 1 + min(enddist[i], enddist[j]) >= startdist[d]) ans++;
}
cout << ans << endl;
}
/*
5 4 1 5
1 2
2 3
3 4
4 5
*/
知识点:贪心
思路:我们发现参赛者每多参加一场比赛,都会在参赛前无形中添加一条其等级的约束(参加 A A A 组比赛说明其等级不得小于 1900 1900 1900;参加 B B B 组比赛说明其等级不得大于 1899 1899 1899 )
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long
#define db double
#define VI vector<int>
#define PII pair<int, int>
const db Pi = 3.141592653589793;
const int INF = 0x7fffffff;
const int N = 1e5 + 5;
const db eps = 1e-10;
int n, c, d, have2;
ll minn, maxn;
int main(){
cin >> n;
minn = -INF, maxn = INF, have2 = 0;
rep(i, 1, n){
cin >> c >> d;
if(d == 1){
if(maxn < 1900){
puts("Impossible");
return 0;
}
if(minn < 1900) minn = 1900; //更新
minn += c, maxn += c;
}
else if(d == 2){
have2 = 1;
if(minn >= 1900){
puts("Impossible");
return 0;
}
if(maxn > 1899) maxn = 1899; //更新
maxn += c, minn += c;
}
}
if(!have2) puts("Infinity");
else cout << maxn << endl;
}
/*
3
-7 1
5 2
8 2
*/
思路:假设一个区间 [ a x , a y ] [a_x,a_y] [ax,ay] 满足要求,则按照要求有
a x ⊕ a x + 1 ⊕ . . . ⊕ a y = ( a x ⊕ . . . ⊕ a m i d ) ⊕ ( a m i d + 1 ⊕ . . . ⊕ a y ) = x ⊕ x = 0 a_x\oplus a_{x+1}\oplus ...\oplus a_y=(a_x\oplus ...\oplus a_{mid})\oplus (a_{mid+1}\oplus ...\oplus a_y)=x\oplus x=0 ax⊕ax+1⊕...⊕ay=(ax⊕...⊕amid)⊕(amid+1⊕...⊕ay)=x⊕x=0
于是若 y − x + 1 y-x+1 y−x+1 为偶数且 a x ⊕ a x + 1 ⊕ . . . ⊕ a y = 0 a_x\oplus a_{x+1}\oplus ...\oplus a_y=0 ax⊕ax+1⊕...⊕ay=0 ,则其此区间一定满足要求。
证明:可以按位拆开考虑,当一位被区间内所有元素异或后为 0 0 0,表示一定有偶数个元素在这一位的位置为 1 1 1。将这偶数个元素分成两两一对,那每一对 1 1 1 可以共同在区间的前后两部分,或者分别在区间的前后两部分。这两种分发都导致这一对 1 1 1 使得区间两部分的异或和在这一位贡献相同,故前后两部分元素的异或和一定相同。
VI Xor[3][1 << 21]
不要开小了。#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long
#define db double
#define VI vector<int>
#define PII pair<int, int>
const db Pi = 3.141592653589793;
const int INF = 0x7fffffff;
const int N = 3e5 + 5;
const int NN = (1 << 21);
const db eps = 1e-10;
int n, a[N], sum[N], vis[NN];
ll ans;
VI Xor[3][NN];
int main(){
scanf("%d", &n);
memset(vis, 0, sizeof(vis));
rep(i, 1, n){
scanf("%d", &a[i]);
sum[i] = (i == 1 ? a[i] : sum[i - 1] ^ a[i]);
Xor[(i % 2) ? 1 : 0][sum[i]].push_back(i);
vis[sum[i]] = 1;
}
Xor[0][0].push_back(0);
ans = 0;
rep(i, 0, NN - 1){
if(!vis[i]) continue;
rep(k, 0, 1){
VI tmp = Xor[k][i];
if(!tmp.size()) continue;
ans += (ll)tmp.size() * ((ll)tmp.size() - 1) / 2; //直接算
}
}
cout << ans << endl;
}
/*
5
1 2 3 4 5
*/
知识点:动态规划
思路:分为奇偶两种情况讨论。设 f [ i ] f[i] f[i] 表示前 i i i 个数字中选择 ⌊ i 2 ⌋ \lfloor\dfrac{i}{2}\rfloor ⌊2i⌋ 个两两不相邻数字的最大可能和,来线性动态规划求 f [ n ] f[n] f[n]
f[i] = max(f[i - 2] + a[i], sum[i - 1])
.#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long
#define db double
#define VI vector<int>
#define PII pair<int, int>
const db Pi = 3.141592653589793;
const int INF = 0x7fffffff;
const int N = 2e5 + 5;
const db eps = 1e-10;
ll n, a[N], sum[N], f[N];
int main(){
cin >> n;
rep(i, 1, n){
cin >> a[i];
sum[i] = a[i] + (i > 2 ? sum[i - 2] : 0);
}
f[1] = 0; //不能写 max(0ll, a[1]), 因为 1 / 2 = 0
rep(i, 2, n){
if(i % 2) f[i] = max(f[i - 2] + a[i], f[i - 1]);
else f[i] = max(f[i - 2] + a[i], sum[i - 1]); //偶数时一定要考虑 sum[i - 1] 的情况
}
cout << f[n] << endl;
}
/*
27
18 -28 18 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49
-77 57 24 -70 -93 69 -99 59 57 -49
*/
知识点:并查集
思路:重点可以任意(无限)次交换操作,(自己试试)发现若一堆位置互相相连(可交换),则每个数字一定可以换到同一堆的任意一个位置,则若 a [ i ] a[i] a[i] 与 i i i 相连,则 a [ i ] a[i] a[i] 一定可以换到 a [ i ] a[i] a[i] 对应数值的位置。
//可以任意次交换,于是在一团中的一定可以换到想去的位置
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long
#define db double
#define VI vector<int>
#define PII pair<int, int>
const db Pi = 3.141592653589793;
const int INF = 0x7fffffff;
const int N = 1e5 + 5;
const db eps = 1e-10;
int n, m, a[N], pre[N];
ll ans = 0;
int find(int x){
if(pre[x] == x) return x;
return pre[x] = find(pre[x]);
}
void join(int x,int y){
int fx = find(x), fy = find(y);
if(fx != fy) pre[fx] = fy;
}
int main(){
cin >> n >> m;
rep(i, 1, n){
cin >> a[i];
pre[i] = i;
}
rep(i, 1, m){
int x, y; cin >> x >> y;
join(x, y);
}
rep(i, 1, n) if(find(i) == find(a[i])) ans++;
cout << ans << endl;
}
/*
5 2
5 3 1 4 2
1 3
5 4
*/
知识点:数学(素数)
题目:求十进制 n n n 的阶乘 n ! n! n! 在 m m m 进制表示法后面有多少零。
思路: n 10 ! n_{10}! n10! 在 m m m 进制下有 t t t 个零表示 m t ∣ n ! 且 m t + 1 ∤ n ! \color{red}m^t|n! \;且\; m^{t+1}\not |n! mt∣n!且mt+1∣n!
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long
#define db double
#define VI vector<int>
const int N = 1e5 + 5;
ll n, m, cnt = 0, ans, tmp;
struct AC{
ll p, num, real;
}a[N];
int main(){
cin >> n >> m;
ll y = m;
rep(i, 2, sqrt(m)){
if(y % i == 0){
tmp = 0;
while(y % i == 0) y /= i, tmp++;
a[++cnt].p = i, a[cnt].num = tmp;
}
}
if(y != 1) a[++cnt].p = y, a[cnt].num = 1;
rep(i, 1, cnt){
tmp = 0;
for(ll j = n; j; j /= a[i].p) tmp += j / a[i].p; //log(n) 计算 n! 中有多少个 a[i].p
a[i].real = tmp;
}
ans = (1ll << 62);
rep(i, 1, cnt) ans = min(ans, a[i].real / a[i].num);
cout << ans << endl;
}
/*
6 9
*/
文章浏览阅读67次。说明:本程序演示如何利用log4net记录程序日志信息。log4net是一个功能著名的开源日志记录组件。利用log4net可以方便地将日志信息记录到文件、控制台、Windows事件日志和数据库(包括MS SQL Server, Access, Oracle9i,Oracle8i,DB2,SQLite)中。并且我们还可以记载控制要记载的日志级别,可以记载的日志类别包括:FATAL(致命错误..._log.net system.configuration.ignoresectionhandler
文章浏览阅读947次。git修改了.gitignore文件没有生效_git 修改文件不变化
文章浏览阅读2k次,点赞2次,收藏5次。测试环境和生产环境表结构不一致?试试这款数据库Schema生成工具Screw工具_数据库表结构文档生成工具
文章浏览阅读228次。1. 两数之和给定一个整数数组nums和一个目标值target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。示例:给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]解决:var twoSum = function(nums, target) { for(..._题目描述 给定一个长度为n的数组s,还给定一个目标值m。从数组s中挑选3个数,使得这
文章浏览阅读2.1k次,点赞3次,收藏3次。Spring Boot - @ResponseStatus 和 @ExceptionHandler_@responsestatus exceptionhandler
文章浏览阅读2.3k次,点赞3次,收藏3次。在spring cloud 的使用的时候,我发现测试起来很不方便,需要使用Postman等类似的工具来调用我们的接口,这显然是很麻烦的,那么有没有一种方式可以让我们在gateway里使用swagger来测试呢。答案是肯定的,我查阅资料发现了之前有人实现了zuul网关的聚合swagger,通过他的思路我自己写了一些类,首先需要,在gateway网关中创建三个类,下面贴出来SwaggerHandl..._springcloud gateway 整合swagger
文章浏览阅读2.3w次。首先打开phpstudy的网站栏点击创建网站,新建一个网站(域名随便输反正是局域网)然后点击确认。然后网站好了,就可以新建项目,打开phpstorm,然后点击new project新建项目,然后再在刚刚打开的站点添加/phpinfo.php,看到如下页面,即我们的php环境搭建完成。然后在location栏里选择项目路径,就是刚刚我们创建的那个站点的路径。这个是问你文件夹不是空的是否在这个非空文件夹创建项目,点击创建就好。打开浏览器输入刚刚创建网站时输入的域名,即可看见我们的网站。如下,网站便创建好了。_怎么搭建web,php环境
文章浏览阅读1.2k次。高通SDX12 sar sensor AW9610x_aw9610
文章浏览阅读949次。微信小程序登录+后台获取oppenId+微信的授权微信小程序登录 wx.login({ success(res) { wx.request({ url: '', //填入你自己的请求url method:"", data:{ code:res.code, ..._获取微信oppenid
文章浏览阅读651次。2001年2月3日,吕梁在他的北京亚运村北辰花园别墅被警方逮捕,他是当时的著名企业家兼顶级股评人,被捕的理由是涉嫌操纵一系列股票的股价,给股民造成了超过50亿元的损失。对于警察的到来,吕梁一点也不感到惊恐,正相反,他长长舒了一口气,脸上则露出了轻松的微笑。对于他为何如此反常,一位财经评论人解释道,“他(吕梁)此时觉得待在大牢里比待在外面被人追杀更安全。”想要“追杀”吕梁的人据说是他的合作伙..._我国打击股市坐庄的第一例
文章浏览阅读42次。nginx.confuser root; # 执行nginx 用户events { worker_connections 1024;}http { include /etc/nginx/mime.types; # 识别文件类型, 防止被转化为文本类型 解决css 无法生效的问题 default_type application/octet-stream;server..._ecdhe:dhe:!adh:!export56
文章浏览阅读834次。这篇文章是一个技术伙伴写的,经过他授权,放到小专栏里面。效果图如下:Openlayers绘制带箭头的路线只用到了ol.FeatureStyleFunction,简单易懂,详细步骤及代码如下:第一步,创建线要素: var line_feature = new ol.Feature(); var line_geom=new ol.geom.LineString(paths); line..._openlayer 3d地图