即 重现 2019 ICPC North American Qualifier Contest
A.Circuit Math 【模拟】
题意： 给出每个变量的真值， 问逻辑电路最后的输出结果。
数据结构后缀表达式求值， 借助栈来实现， 最后栈中的元素就是答案。
【我用30存了一个T， 31存了一个F， 方便写】
#include<bits/stdc++.h>
using namespace std;
const int N = 50;
bool book[N];
int n;
char c;
int main(){
cin >> n;
book[30] = 1, book[31] = 0;
for(int i = 1; i <= n; ++ i){
scanf(" %c", &c);
if(c == 'T') book[i] = 1;
else book[i] = 0;
}
stack<int> s; getchar();
while((c = getchar()) != EOF){
if(c == ' ') continue;
//printf("c = %c\n", c);
if(isalpha(c)) s.push(c - 'A' + 1);
else if(c == '*'){
int t1 = s.top(); s.pop();
int t2 = s.top(); s.pop();
//printf("t1 = %d t2 = %d\n", t1, t2);
int ans;
if(book[t1] && book[t2]) ans = 1;
else ans = 0;
s.push(ans == 1 ? 30 : 31);
// printf("ans = %d\n", ans);
}else if(c == '+'){
int t1 = s.top(); s.pop();
int t2 = s.top(); s.pop();
//printf("t1 = %d t2 = %d\n", t1, t2);
int ans;
if(!book[t1] && !book[t2]) ans = 0;
else ans = 1;
//printf("ans = %d\n", ans);
s.push(ans == 1 ? 30 : 31);
}else if(c == '-'){
int t = s.top(); s.pop();
int ans = book[t];
s.push(ans == 1 ? 31 : 30);
//printf("ans = %d\n", ans);
}
}
cout << (book[s.top()] == 1 ? "T" : "F");
return 0;
}B. Diagonal Cut 【思维】
题意：给一个M * N的蛋糕， 从左下-右上对角线切一刀， 问有多少个小方格面积被恰好1分为2.
思路：对角线的斜率为N/M. 如果一个小正方形的中心在对角线上，那一定能被一分为二。所以转化成如何求有多少小正方形的中心在对角线。
在直角坐标系中，(i, j)的正方形中心坐标是(i-1/2, j-1/2)，由斜率可以化简得到：
2i-1/2j-1 = N/M. 所以必须保证N M都是奇数才有解， 否则就是无解。(因为左边的分子分母都是奇数，右边已经约分过，不可能是两个偶数，只有都是奇数才会有解), 解的数量就是gcd(N,M).
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n, m;
ll gcd(ll a, ll b){
return b ? gcd(b, a % b) : a;
}
int main(){
cin >> n >> m;
ll g = gcd(n, m);
n /= g, m /= g;
if(n % 2 == 0 || m % 2 == 0) cout << 0;
else cout << g;
return 0;
}C.Gerrymandering【阅读理解， 模拟】
题意： 输出每行的第一个数表示选举票数最多的人（A或B），第二个数表示A 浪费的票数，第三个数表示B 浪费的
票数。最后一个小数，应该将A 在各个地区获得的总票数与B 在各个地区的总票数的差值，将这个差值
除以 A和B 所有的总票数。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1010;
int p, d, wasteA, wasteB, total;
struct node{
int A, B, wa, wb;
}book[N];
int main(){
cin >> p >> d;
while(p --){
int x, a, b;
cin >> x >> a >> b;
book[x].A += a;
book[x].B += b;
}
for(int i = 1; i <= d; ++ i){
int tmp = (book[i].A + book[i].B) / 2 + 1;
if(book[i].A > book[i].B) book[i].wa = book[i].A - tmp, book[i].wb = book[i].B;
else book[i].wb = book[i].B - tmp, book[i].wa = book[i].A;
total += book[i].A + book[i].B;
wasteA += book[i].wa;
wasteB += book[i].wb;
}
for(int i = 1; i <= d; ++ i){
printf("%c %d %d\n", (book[i].A > book[i].B ? 'A' : 'B'), book[i].wa, book[i].wb);
}
printf("%.10lf", (double)abs(wasteA - wasteB) / total);
return 0;
} D. Missing Numbers【签到】
题意： 问从1到最大的数中没出现的数，并输出。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1010;
int a[N], n, maxx;
int main(){
cin >> n;
bool f = 0;
for(int i = 1; i <= n; ++ i){
int x;
cin >>x;
a[x] = 1;
maxx = max(maxx, x);
}
for(int i = 1; i <= maxx; ++ i){
if(!a[i]) f = 1, cout << i << endl;
}
if(!f) puts("good job");
return 0;
} I. Slow Leak【思维，建图方式， 最短路的综合应用】
太妙了太妙了wwww
题意：1号起点，n号终点。自行车车胎损坏，加满气只能最多走d公里。 路上某些点是加气站， 可以把气冲满。初始时气是满的，问能否到达终点以及能到的最短路。
思路：这个题是没法直接用dijkstra在里面修改的， 因为并不是边权是第一排序关键字， 气是第二关键字。有的时候会故意走远路为了加气。
所以先用flyod预处理每个点之间的最短路（不考虑气的问题）， 然后重新建图，只保留终点、起点以及所有的加气站，边是这些点之间的边，边权是他们之间的最短路(为了方便处理， 大于d的边可以不建)。然后在新图上跑一遍dijkstra求最短路即可。【因为新图全是加气站，就不用考虑加气的问题了，每到一个点就把气加满】。 思路还是tql
tips: 这题会爆int， 所以初始化mp dis的时候不能用0x3f(太小了)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 510, M = 250010;
const ll inf = 1e18;
ll mp[N][N],dis[N],w[M],d;
int n,m,G[N],q;
int idx, ne[M], e[M], h[N];
bool st[N];
void add(int a, int b, int c){ e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;}
struct node{
int u; ll d;
bool operator < (const node& rhs) const{
return d > rhs.d;
}
};
void flyod(){
for(int k = 1; k <= n; ++ k)
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j)
if(mp[i][j] > mp[i][k] + mp[k][j])
mp[i][j] = mp[i][k] + mp[k][j];
}
void dijkstra(int u){
for(int i = 1; i <= n; ++ i) dis[i] = inf;
dis[u] = 0;
priority_queue<node> q;
q.push(node{u, 0});
while(!q.empty()){
node fr = q.top(); q.pop();
int u = fr.u;
if(st[fr.u]) continue;
st[fr.u] = true;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(dis[j] > dis[u] + w[i]){
dis[j] = dis[u] + w[i];
q.push(node{j, dis[j]});
}
}
}
if(dis[n] == inf) puts("stuck");
else cout << dis[n];
}
int main(){
cin >> n >> m >> q >> d;
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j)
mp[i][j] = (i == j ? 0 : inf);
for(int i = 1; i <= q; ++ i){
int x;
cin >> x;
G[x] = 1;
}
for(int i = 1; i <= m; ++ i){
int a, b, c;
cin >> a >> b >> c;
mp[a][b] = mp[b][a] = c;
}
flyod();
memset(h, -1, sizeof h);
for(int i = 1; i <= n; ++ i){
if(i == 1 || i == n || G[i]){
for(int j = i + 1; j <= n; ++ j){
if(mp[i][j] > d) continue ;
if(G[j] || j == n) add(i, j, mp[i][j]), add(j, i, mp[i][j]);
}
}
}
dijkstra(1);
return 0;
}J. Stop Counting!【前缀和 思维】
题意：给一个数组，可以选择去掉其中一段连续的序列（可以全部去掉），使得剩余部分的平均值最大。
思路：求一遍前缀和，同时维护最大pre_avg, 再反向求一遍， 维护一个sub_avg。 两者最大的就是答案（如果都比0小，就是0，全删掉）。
可以贪心的解： 假如去掉中间的C段， 留下两边的A和B：
A C B, 此时， 如果A比B大，那会连同B一起删掉； 反之亦然。所以不可能只删掉中间的某一段而留下后面的【可以认为A B两段除非平均值相等， 否则小的一定会拖累大的，不如删掉； 而平均值相等的话，没任何影响。】
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1000010;
ll a[N],n,sum1,sum2;
double ave, minn = 1e18, maxa = 0, maxb = 0;
int main(){
cin >> n;
for(int i = 1; i <= n; ++ i){
scanf("%lld", &a[i]);
sum1 += a[i];
ave = (double)sum1 / i;
maxa = max(maxa, ave);
}
for(int i = n; i >= 1; -- i){
sum2 += a[i];
ave = (double)sum2 / (n - i + 1);
maxb = max(maxb, ave);
}
printf("%.10lf", max(maxa, maxb));
return 0;
}K. Summer Trip【复杂度估计， 思维， 暴力？】
题意：从一个只有大写字母的字符串中求得符合以下要求的字符串数量：
1.字符串中至少含有2个不同字母；
2.连续的一段
3.首尾字符在选出的子串中只出现一次。
思路：会想到一个O(N2)的暴力， 但是1e5肯定会超时。 可以发现，如果固定起点的话，只要向后遍历到一个和起点相同的字母，就可以停止匹配（因为之后的字符串首字母一定出现了>=2次了）。因为只有大写， 所以最坏情况也只会向后遍历26次， 所以复杂度实际是O(26n).
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100010;
int n,ans;
char s[N];
int main(){
scanf("%s", s + 1);
n = strlen(s + 1);
for(int i = 1; i <= n; ++ i){
int book[30] = {0};
book[s[i] - 'a'] = true;
for(int j = i + 1; j <= n; ++ j){
if(s[j] == s[i]) break;
if(!book[s[j] - 'a']) ans ++;
book[s[j] - 'a'] = true;
}
}
cout << ans;
return 0;
}M. Zipline【数学， 二分， 求导】
题意：看图说话8
思路：求出绳子长度的表达式，求导，当导数为0的时候最大。
所以可以二分找导函数的零点。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100010;
int t;
double w,g,h,r,eps = 1e-6;
double f(double x){
return sqrt(x * x + (g - r) * (g - r)) + sqrt((h - r) * (h - r) + (w - x) * (w - x));
}
double ff(double x){
return x / sqrt(x * x + (g - r) * (g - r)) + (x - w) / sqrt((h - r) * (h - r) + (w - x) * (w - x));
}
void solve(){
cin >> w >> g >> h >> r;
double l = 0, r = w, mid = (l + r) / 2, last = ff(mid);
while(abs(last) > eps){
if(last < 0) l = mid;
else r = mid;
mid = (l + r) / 2;
last = ff(mid);
}
printf("%.8lf %.8lf\n",sqrt(w * w + abs(h - g) * abs(h - g)), f(mid));
}
int main(){
cin >> t;
while(t --) solve();
return 0;
}H.Running Routes【思维， 区间dp】
太妙了wwwww 一个方程很基础的区间Dp, 但是比赛时过得很少， 因为思路不是很好想。
定义dp[i,j]为从i到j这个编号区间中能选择的跑道的最大数目。那么分界点为k, 如果以这个为分界线的话，可以分成(i+1,k-1)|(k+1,j)【保证点不能相交】两个区域，这两个区域只能在彼此的区域内选点【否则就交叉了】， 这样就可以进行区间DP的转移了。
tips:注意第三重循环中k 要从i开始， j结束（闭区间）【这样包括了i点不选和j点不选这两种情况】
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 510;
int mp[N][N], dp[N][N], n, m, ans;
int main(){
//freopen("5.txt", "r", stdin);
cin >> n;
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j)
cin >> mp[i][j];
for(int len = 1; len < n; ++ len)
for(int i = 1; i + len <= n; ++ i){
int j = i + len;
for(int k = i; k <= j; ++ k)
dp[i][j] = max(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j] + mp[i][k]);
}
cout << dp[1][n];
return 0;
}G. Research Productivity Index【概率dp】
题意：小明手里有n份代码，每一份代码都有一个ac成功率。f值等于a^{a/b}，其中a为ac的数量，b为总提交数，比如交了5份4份ac， f = 4^{4/5}≈3.031433 ， 最后问交几份怎么交期望值最大。
思路：dp[i,j]表示前i份中通过j份的概率， 可以递推得到。
要特别注意init的时候dp[0,0]=1， 表示前0份过0份的概率是1， 然后dp[i][i] 要特殊判断。
其余的dp[i,j] = dp[i-1,j] * 当前不通过的概率 + dp[i-1,j-1] * 当前通过的概率。
预处理dp数组后，枚举交i份过j份的得分， 实时更新ans即可。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 110;
int n,a[N];
double p[N],ans,dp[N][N];
int main(){
cin >> n;
for(int i = 1; i <= n; ++ i) cin >> a[i];
sort(a + 1, a + 1 + n, greater<int>());
for(int i = 1; i <= n; ++ i) p[i] = 1.0 * a[i] / 100; //预处理
dp[0][0] = 1;
for(int i = 1; i <= n; ++ i){
dp[i][0] = dp[i - 1][0] * (1 - p[i]);
for(int j = 1; j < i; ++ j)
dp[i][j] = dp[i - 1][j - 1] * p[i] + dp[i - 1][j] * (1 - p[i]);
dp[i][i] = dp[i - 1][i - 1] * p[i];
}
for(int i = 1; i <= n; ++ i){
double res = 0;
for(int j = 1; j <= i; ++ j)
res += pow(j, 1.0 * j / i) * dp[i][j];
ans = max(ans, res);
}
printf("%.10lf", ans);
return 0;
}
京公网安备 11010502036488号