2018-2019 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)

2018-2019 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)

思路:

A?Exam

思路:水題

代碼:

#include<bits/stdc++.h>
using namespace std;
int main(){int k;scanf("%d",&k);char s1[1010],s2[1010];scanf("%s%s",s1,s2);int same=0;int n=strlen(s1);for(int i=0;i<n;i++){same+=s1[i]==s2[i];}cout<<min(same,k)+min(n-same,n-k)<<endl;return 0;
}
View Code

?

B?Coprime Integers

思路:容斥

代碼:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//headconst int N = 1e7 + 5;
LL g[N];
LL solve(int a, int b) {if(a > b) swap(a, b);if(a == 0) return 0;for (int i = a; i >= 1; i--) {g[i] = 1LL * (a/i) * (b/i);for (int j = i+i; j <= a; j += i) g[i] = g[i] - g[j];}return g[1];
}
int main() {int a, b, c, d;scanf("%d %d %d %d", &a, &b, &c, &d);printf("%lld\n", solve(b, d) - solve(b, c-1) - solve(a-1, d) + solve(a-1, c-1));return 0;
}
View Code

?

C?Contest Setting

思路:dp

dp[i][j]表示前i種選j個的方案數

代碼:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//headconst int MOD = 998244353;
const int N = 1e3 + 5;
LL dp[N][N];
int cnt[N], a[N], tot = 0;
map<int, int> mp;
int main() {int n, k;scanf("%d %d", &n, &k);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);if(mp.find(a[i]) == mp.end()) mp[a[i]] = ++tot, cnt[tot] = 1;else cnt[mp[a[i]]] ++;}dp[0][0] = 1;for (int i = 1; i <= tot; i++) {for (int j = 0; j <= k; j++) dp[i][j] = dp[i-1][j];for (int j = 1; j <= k; j++) dp[i][j] = (dp[i][j] + dp[i-1][j-1]*cnt[i]) % MOD;}printf("%lld\n", dp[tot][k]);return 0;
}
View Code

?

D?Count The Bits

思路:dp

dp[i][j][0]表示前i位構成的數中對k取模為j的數的個數

dp[i][j][1]表示前i位構成的數中對k取模為j的數中二進制中1的個數

代碼:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//headconst int N = 150, M = 1e3 + 5;
const int MOD = 1e9 + 9;
LL dp[N][M][2];
int main() {int k, b;scanf("%d %d", &k, &b);dp[0][0][0] = 1;dp[0][0][1] = 0;for (int i = 1; i <= b; i++) {for (int j = 0; j < k; j++) {(dp[i][(j*2)%k][0] += dp[i-1][j][0]) %= MOD;(dp[i][(j*2+1)%k][0] += dp[i-1][j][0]) %= MOD;(dp[i][(j*2)%k][1] += dp[i-1][j][1]) %= MOD;(dp[i][(j*2+1)%k][1] += dp[i-1][j][1] + dp[i-1][j][0]) %= MOD;}}printf("%lld\n", dp[b][0][1]);return 0;
}
View Code

?

E?Cops And Roobers

F?Rectangles

G?Goat on a Rope

思路:求點到矩形的最近距離

代碼:

#include<bits/stdc++.h>
using namespace std;
double cal(double x1,double y1,double x2,double y2)
{return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{double x,y,x1,x2,y1,y2,ans=1e9;scanf("%lf%lf%lf%lf%lf%lf",&x,&y,&x1,&y1,&x2,&y2);if(x>=min(x1,x2)&&x<=max(x2,x1)) ans=min(abs(y1-y),abs(y2-y));else if(y>=min(y1,y2)&&y<=max(y1,y2)) ans=min(abs(x-x1),abs(x-x2));else ans=min(cal(x,y,x1,y1),min(cal(x,y,x2,y2),min(cal(x,y,x1,y2),cal(x,y,x2,y1))));printf("%.3f\n",ans);
}
View Code

?

H?Repeating Goldbachs

思路:暴力

代碼:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//headconst int N = 1e6 + 5;
int p[N], tot = 0;
bool not_p[N];
void seive() {for (int i = 2; i < N; i++) {if(!not_p[i]) {p[++tot] = i;}for (int j = 1; j <= tot && p[j]*i < N; j++) {not_p[p[j]*i] = true;if(i % p[j] == 0) break;}}
}
int main() {int x;scanf("%d", &x);seive();int ans = 0;while(x >= 4) {for(int i = 1; i <= tot && p[i] <= x; i++) {if(!not_p[x-p[i]]) {x = x - p[i] - p[i];ans++;break;}}}printf("%d\n", ans);return 0;
}
View Code

?

I?Inversions

J?Time Limits

思路:水題

代碼:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//headconst int N = 105;
int t[N];
int n, s;
int main() {scanf("%d %d", &n, &s);for (int i = 1; i <= n; i++) scanf("%d", &t[i]);sort(t+1, t+1+n);printf("%d\n", (t[n]*s + 999) / 1000);return 0;
}
View Code

?

K?Knockout

L?Liars

思路:暴力

代碼:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//headconst int N = 1e3 + 5;
pii a[N];
int main() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d %d", &a[i].fi, &a[i].se);int ans = -1;for (int i = 0; i <= n; i++) {int cnt = 0;for (int j = 1; j <= n; j++) {if(a[j].fi <= i && i <= a[j].se) cnt++;}if(cnt == i) ans = max(ans, i);}printf("%d\n", ans);return 0;
}
View Code

?

M?Mobilization

?

轉載于:https://www.cnblogs.com/widsom/p/10007965.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/537441.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/537441.shtml
英文地址，請注明出處：http://en.pswp.cn/news/537441.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

python random()*10的值不可能是_Python

python random()*10的值不可能是_Python

Python 生成隨機數、隨機字符串 #!/usr/bin/python # -*- coding: UTF-8 -*- import random import string # 隨機整數&#xff1a; print random.randint(1,50) # 隨機選取0到100間的偶數&#xff1a; print random.randrange(0, 101, 2) # 隨機浮點數&#xff1a; print rand…
閱讀更多...
Prince2與PMP的區別

Prince2與PMP的區別

p2有7個原則&#xff0c;7個主題&#xff0c;7個流程&#xff0c;即37二十一。 P2有26個管理產品模板。 2009版本是經典版本&#xff0c;2017版本與2009版本內容基本沒變&#xff0c;梳理了目錄&#xff0c;使內容更加有可讀性。 P2是非常好的項目管理方法論&#xff0c;任何…
閱讀更多...
html實體編碼_深入研究瀏覽器解析和XSS有效負載編碼

html實體編碼_深入研究瀏覽器解析和XSS有效負載編碼

翻譯文章&#xff0c; 原文&#xff1a;Deep dive into browser parsing and XSS payload encoding[1]這篇博客文章將深入探討HTML&#xff0c;URL和JavaScript的規范和解析器&#xff0c;以及它們之間的交互如何在跨站點腳本轉義中有所作為。對于您而言&#xff0c;這可能很難…
閱讀更多...
2021-02-03-延長一天時間的有效方法

2021-02-03-延長一天時間的有效方法

方法1&#xff1a;給對的事情花時間 分清事情輕重緩急&#xff0c;做了對的事情會讓人感到開心。有個原則&#xff0c;就是事后回想這件事&#xff0c;會讓自己感到開心。 比如玩了一晚上游戲和學習&#xff0c;可能更多人的開心是后者。 比如健身運動與長時間學習&#xff…
閱讀更多...
[洛谷P1341]無序字母對

[洛谷P1341]無序字母對

題目大意&#xff1a;給一張無向圖&#xff0c;找一條字典序最小的歐拉路徑 題解&#xff1a;若圖不連通或有兩個以上的奇數點&#xff0c;則沒有歐拉路徑&#xff0c;可以$dfs$&#xff0c;在回溯時把這個節點加入答案 卡點&#xff1a;沒有在回溯時加入答案&#xff0c;導致出…
閱讀更多...
產品部門四大角色——PM/PD/UE/UI

產品部門四大角色——PM/PD/UE/UI

按照產品從規劃到最終成型的任務流方向&#xff0c;從抽象到具體、商業到技術的過程&#xff0c;涉及產品經理、產品設計師、用戶體驗師、視覺設計師四個角色。 PM&#xff1a;產品經理&#xff0c;俗稱老大。一個產品&#xff0c;首先由PM來分析細分市場、目標客戶的訴求&…
閱讀更多...
拉取遠程分支_git clone切換分支步驟，代理設置，作者信息設置

拉取遠程分支_git clone切換分支步驟，代理設置，作者信息設置

1.克隆遠程倉庫git clone git地址2.查看所有分支git branch –a3.切換分支git checkout branchName4.查看當前所在分支git branch5.拉取代碼git pull6.提交代碼git add file/folder git commit -m comment git push可能遇到的問題&#xff1a;A.error: fatal: unable to acce…
閱讀更多...
[學習筆記]半平面交

[學習筆記]半平面交

一個直線把平面分成兩部分&#xff0c;就是兩個半平面 處理這兩個平面的交的信息&#xff0c;就是半平面交 推薦&#xff1a; 計算幾何之半平面交算法模板及應用 bzoj 2618 半平面交模板學習筆記 【總結】半平面交 可以用于求任意多邊形交&#xff0c;任意多邊形內核。 &#x…
閱讀更多...
Project計算項目進度

Project計算項目進度

1.設立根節點 2.資源列表 3.資源成本 4.基準 在任務分配狀況 視圖里&#xff0c;添加“基線工時”“實際工時”“BCWS(計劃&#xff09;”“ACWP(實際&#xff09;”“BCWP&#xff08;掙值&#xff09;”&#xff0c;“SV(>0 提前&#xff0c;<0 延后&#xff09;”、…
閱讀更多...
jquery動態綁定事件的方法_Jquery綁定事件及動畫效果

jquery動態綁定事件的方法_Jquery綁定事件及動畫效果

綁定事件bind(type, data, fuc)one(type, data, fuc) //只執行一次常見事件類型名稱含義blur失去焦點focus獲得焦點load加載resize重置大小scroll滾動unload卸載click點擊dblclick雙擊mousedown鼠標按下mouseup鼠標彈起mousemove鼠標移動mouseover鼠標懸停mouseout鼠標移走mous…
閱讀更多...
需求調研前的準備工作

需求調研前的準備工作

1.需求調研前需要做哪些準備&#xff1f; 1.從各種渠道了解客戶所在行業的行業信息&#xff1b; 2.向和對方有過業務接觸的同事了解對方的信息如現哪些系統和業務流程、對方的管理組織結構是怎樣的&#xff1b; 3.是否可以搜集到對方的一些文字情信息如業務單據、管理規范等。 …
閱讀更多...
實驗 5 編寫、調試具有多個段的

實驗 5 編寫、調試具有多個段的

實驗任務 &#xff08;1&#xff09; &#xff08;2&#xff09; &#xff08;3&#xff09; &#xff08;4&#xff09; 若將最后一條指令”end start“改為”end“&#xff0c;&#xff08;3&#xff09;中的程序仍然可以正常執行。 原因&#xff1a;如果不指明程序的入口&am…
閱讀更多...
hbuilderx的快捷鍵整理pdf_mac鍵盤快捷鍵詳解，蘋果電腦鍵盤快捷鍵圖文教程

hbuilderx的快捷鍵整理pdf_mac鍵盤快捷鍵詳解，蘋果電腦鍵盤快捷鍵圖文教程

作為 Apple 最成熟的系統之一&#xff0c;macOS 已經成為許多人每天都在接觸的生產力工具。為了幫助大家更好地了解 macOS 的生態魅力&#xff0c;我們整理了這份融合了文字圖片和動圖的mac鍵盤快捷鍵詳解&#xff0c;希望能夠幫助你掌握更多系統使用技巧。文章所有操作都基于 …
閱讀更多...
word插入圖片顯示不全

word插入圖片顯示不全

word插入圖片&#xff0c;顯示不全&#xff0c;只有部分。 調整步驟 圖片尾部 光標定位到圖片的尾部 單倍行距 右鍵&#xff0c;選擇“段落”&#xff0c;行間距選擇“單倍行距” 圖片就完成顯示了
閱讀更多...
理解 JavaScript 作用域

理解 JavaScript 作用域

上一篇文章中分析了 JS 中的數據類型和變量。這一篇文章將分析作用域&#xff0c;以及回答上一篇文章中變量提升的原因。 什么是作用域 作用域是一套規則&#xff0c;保存著變量&#xff0c;等待被引擎所查找。 var a 1; console.log(a); // > 1 console.log(b); // >…
閱讀更多...
mysql行求和

mysql行求和

SELECT 列1 列2 列3 …… 列N AS Total FROM 表 SELECT sum(列1 列2 列3 …… 列N) AS Total FROM 表 轉載于:https://www.cnblogs.com/weilovehua/p/10024624.html
閱讀更多...
python安裝后在哪里找_python安裝后的目錄在哪里

python安裝后在哪里找_python安裝后的目錄在哪里

從官網下載python的安裝包&#xff0c;安裝過程中可選擇裝在C盤或D盤或者其他的磁盤。 如果忘記了安裝在哪里&#xff0c;可以在命令行中使用以下命令 where python 會顯示python的絕對路徑 C:\Users\Administrator>where python C:\Users\Administrator\AppData\Local\Prog…
閱讀更多...
Axure原型設計導出到PDF文件

Axure原型設計導出到PDF文件

Axure 沒有直接導出PDF文件的功能&#xff0c;可以通過Axure 的打印功能&#xff0c;選擇PDF打印機&#xff0c;以間接的方式將原型設計導出到pdf文件里。 操作步驟 以Axure9為例 打印 Axure9---文件---打印 不要母版 預覽 預覽下效果&#xff0c;看下是否有不必要的內容 …
閱讀更多...
izoak028

izoak028

離散數學 &#xff08;自考&#xff09; 【自考】計算機網絡原理精講(2018版)轉載于:https://www.cnblogs.com/qianyindichang2/p/10025538.html
閱讀更多...
Word查找替換詳細用法及通配符一覽表

Word查找替換詳細用法及通配符一覽表

使用通配符 要查找“?”或者“*”&#xff0c;可輸入“\?”和“\*”&#xff0c;\1\2\3依次匹配數對括號內容 查找(a)12(b) 替換\2XY\1 結果&#xff1a;bXYa ([.0-9]) [MG]B 匹配文件大小&#xff0c; 例1: 201 MB ,例2: 2.51 GB <(e*r)> 匹配“…
閱讀更多...
最新文章

Copyright @ 2022~2023