博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
2017-2018 ACM-ICPC, Asia Tsukuba Regional Contest
阅读量：6342 次
发布时间：2019-06-22

本文共 10309 字，大约阅读时间需要 34 分钟。

A 

思路:暴力枚举黑巧克力的个数和厚黑巧克力的个数

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       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
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #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);//headLL C(int n, int m) {    LL res = 1;    if(n-m < m) m = n-m;    for (int i = 1; i <= m; i++) {        res *= (n-i+1);        res /= i;    }    return res;}int main() {    int l, k;    LL res = 1;    scanf("%d %d", &l, &k);    LL ans = 0;   for (int i = 1; i <= 51; i++) {        for (int j = 0; j <= i; j++) {            if(j*k + (i-j) + i-1 <= l) {                ans += C(i, j);            }        }   }   printf("%lld\n", ans);    return 0;}
View Code

 

B 

思路:预处理+暴力

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       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
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #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);//headint a[10], b[10];pii p[20];pii delta[20];int tmp[20][20];piii T[500];int t[500];int vv[500];int main() {    int m;    scanf("%d", &m);    for (int i = 1; i <= m; i++) scanf("%d %d", &p[i].fi, &p[i].se);    int cnt = 0;    for (int i = 1; i <= m; i++) {        for (int j = 1; j <= m; j++) {            if(i == j) continue;            int x = p[i].fi - p[j].fi;            int y = p[i].se - p[j].se;            int d = __gcd(x, y);            x /= d;            y /= d;            if(x > 0 && y < 0) x = -x, y = -y;            T[++cnt].fi.fi = x;            T[cnt].fi.se = y;            T[cnt].se = cnt;            tmp[i][j] = cnt;        }    }    sort(T+1, T+1+cnt);    int now = 1;    t[T[1].se] = now;    for (int i = 2; i <= cnt; i++) {        if(T[i].fi.fi == T[i-1].fi.fi && T[i].fi.se == T[i-1].fi.se) {            t[T[i].se] = now;        }        else {            t[T[i].se] = ++now;        }    }    for (int i = 1; i <= m; i++) {        for (int j = 1; j <= m; j++) {            tmp[i][j] = t[tmp[i][j]];        }    }    int up = (1<
View Code

 

C 

思路:模拟

代码:

#include
      
       using namespace std;typedef long long ll;const int maxn=1e5+5;ll a[maxn];ll mol,den;int main(){    ll n,t;    scanf("%lld%lld",&n,&t);    for(int i=0;i
       
        =0 ? t-pre1-a[i]:-den;        pre1+=a[i];        printf("%lld\n",mol/den+2);    }}
View Code

 

D 

E 

F 

思路:先分别求出每个点到1和2的最短路d1[i], d2[i],

对于一条边u->v, 如果d1[v] + d2[u] + w < 1到2最短路径, 那么肯定是HAPPY

否则看这条边是不是1到2的所有最短路径所构成的无向图中的桥, 如果是桥, 删去后最短路肯定变大, 是SAD, 否则最短路径肯定不变, 是SOSO

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       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
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #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 = 1e5  + 5;const LL INF = 0x3f3f3f3f3f3f3f3f;vector
           
             g[N], rg[N], tg[N];int ans[N], u[N], v[N], w[N], low[N], dfn[N], tot = 0;pii fa[N];LL d1[N], d2[N];priority_queue
            
             , greater
             
               > q;void Dij1(int s) { mem(d1, INF); d1[s] = 0; q.push({ 0, s}); while(!q.empty()) { pli p = q.top(); q.pop(); int u = p.se; if(p.fi > d1[u]) continue; for (pii to : g[u]) { int v = to.fi; int w = to.se; if(d1[u] + w < d1[v]) { d1[v] = d1[u] + w; q.push({d1[v], v}); } } }}void Dij2(int s) { mem(d2, INF); d2[s] = 0; q.push({ 0, s}); while(!q.empty()) { pli p = q.top(); q.pop(); int u = p.se; if(p.fi > d2[u]) continue; for (pii to : rg[u]) { int v = to.fi; int w = to.se; if(d2[u] + w < d2[v]) { d2[v] = d2[u] + w; q.push({d2[v], v}); } } }}void tarjan(int u, pii o) { low[u] = dfn[u] = ++tot; fa[u] = o; for (pii p: tg[u]) { int v = p.fi; if(!dfn[v]) { tarjan(v, {u, p.se}); low[u] = min(low[u], low[v]); } else if(v != o.fi) low[u] = min(low[u], dfn[v]); }}int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d %d %d", &u[i], &v[i], &w[i]); g[u[i]].pb({v[i], w[i]}); rg[v[i]].pb({u[i], w[i]}); } Dij1(1); Dij2(2); for (int i = 1; i <= m; i++) { if(d1[v[i]] + w[i] + d2[u[i]] < d1[2]) ans[i] = 1; else if(d1[u[i]] + w[i] + d2[v[i]] == d1[2]) { tg[u[i]].pb({v[i], i}); tg[v[i]].pb({u[i], i}); } } tarjan(1, { 1, 1}); for (int v = 2; v <= n; v++) { int u = fa[v].fi; int id = fa[v].se; if(low[v] > dfn[u]) ans[id] = 2; } for (int i = 1; i <= m; i++) { if(ans[i] == 1) puts("HAPPY"); else if(ans[i] == 2) puts("SAD"); else puts("SOSO"); } return 0;}
View Code

 

G 

思路:将立体问题转换成平面问题

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       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
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #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);//headchar s[5];int w, l;double f1(double x, double c) {    return sqrt(3)*x + c;}double f2(double x, double c) {    return -sqrt(3)*x + c;}int solve() {    scanf("%s", s);    scanf("%d %d", &w, &l);    if(s[0] == 'B') w += 60;    else if(s[0] == 'C') w += 120;    double y = l * sin(w*pi/180.0);    double x = - l * cos(w*pi/180.0);    while(y > 2*sqrt(3)) y -= 2*sqrt(3);    while(x > 2) x -= 2;    while(x < 0) x += 2;    if(0 <= x && x < 1) {        if(0 <= y  && y <= sqrt(3)) {            if(y > f1(x, 0) && y > f2(x, sqrt(3))) return 4;            else if(y < f1(x, 0) && y < f2(x, sqrt(3))) return 4;            else if(y > f1(x, 0) && y < f2(x, sqrt(3))) {                if(y > sqrt(3)/2.0) return 2;                else return 1;            }            else {                if(y > sqrt(3)/2.0) return 1;                else return 2;            }        }        else {            if(y > f1(x, sqrt(3)) && y > f2(x, 2*sqrt(3))) return 3;            else if(y < f1(x, sqrt(3)) && y < f2(x, 2*sqrt(3))) return 3;            else if(y > f1(x, sqrt(3)) && y < f2(x, 2*sqrt(3))) {                if(y > sqrt(3)*3.0/2.0) return 1;                else return 2;            }            else {                if(y > sqrt(3)*3.0/2.0) return 2;                else return 1;            }        }    }    else {        if(0 <= y  && y <= sqrt(3)) {            if(y > f1(x, -sqrt(3)) && y > f2(x, 2*sqrt(3))) return 3;            else if(y < f1(x, -sqrt(3)) && y < f2(x, 2*sqrt(3))) return 3;            else if(y > f1(x, -sqrt(3)) && y < f2(x, 2*sqrt(3))) {                if(y > sqrt(3)/2.0) return 1;                else return 2;            }            else {                if(y > sqrt(3)/2.0) return 2;                else return 1;            }        }        else {            if(y > f1(x, 0) && y > f2(x, 3*sqrt(3))) return 4;            else if(y < f1(x, 0) && y < f2(x, 3*sqrt(3))) return 4;            else if(y > f1(x, 0) && y < f2(x, 3*sqrt(3))) {                if(y > sqrt(3)*3.0/2.0) return 2;                else return 1;            }            else {                if(y > sqrt(3)*3.0/2.0) return 1;                else return 2;            }        }    }}int main() {    if(solve() == solve()) puts("YES");    else puts("NO");    return 0;}
View Code

 

H 

I 

思路:

第一种就是求对于每个区间,有多少个区间与他相交, 取最大值, 这个用容斥做

第二种贪心求,每次从优先队列里取出右端点最靠前的,与当前区间左端点比较

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       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
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #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 = 2e5 + 10, M = 1e5 + 10;pii a[N];int n, bit[M], btt[M];priority_queue
, greater
> q;void add(int x, int ty) { if(ty == 1) { while(x < M) bit[x]++, x += x&-x; } else { while(x < M) btt[x]++, x += x&-x; }}int sum(int x, int ty) { int ans = 0; if(ty == 1) { while(x) ans += bit[x], x -= x&-x; } else { while(x) ans += btt[x], x -= x&-x; } return ans;}int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d %d", &a[i].fi, &a[i].se); } sort(a+1, a+1+n); for (int i = 1; i <= n; i++) { if(q.empty()) q.push(a[i].se); else { int p = q.top(); if(a[i].fi >= p) { q.pop(); q.push(a[i].se); } else q.push(a[i].se); } } int ans2 = q.size(), ans1 = 0; for (int i = 1; i <= n; i++) { add(a[i].se, 1); add(a[i].fi, 2); } for (int i = 1; i <= n; i++) { int t = n-1 - sum(a[i].fi, 1); t -= (n - sum(a[i].se-1, 2)); ans1 = max(ans1, t);// cout << a[i].fi << " " << a[i].se << " " << t << endl; } printf("%d %d\n", ans1+1, ans2); return 0;}
View Code

 

J 

K 

转载于:https://www.cnblogs.com/widsom/p/10008098.html

你可能感兴趣的文章
Dundas 系列
查看>>
巧用AJAX技术，通过updatePanel控件实现局部刷新
查看>>
20140420技术交流活动总结
查看>>
SaltStack配置salt-api
查看>>
各种情况下block的类型
查看>>
ThinkPHP 3.2.x 集成极光推送指北
查看>>
js作用域链
查看>>
java中如何选择Collection Class--java线程（第3版）
查看>>
为运维人员插上腾飞更远的翅膀！
查看>>
Word 2003中编辑标记与格式标记大讨论
查看>>
调试网页PAIP HTML的调试与分析工具
查看>>
路径工程OpenCV依赖文件路径自动添加方法
查看>>
玩转SSRS第七篇---报表订阅
查看>>
WinCE API
查看>>
Linux常用基本命令[cp]
查看>>
CSS 相对|绝对(relative/absolute)定位系列（一）
查看>>
关于 Nginx 配置 WebSocket 400 问题
查看>>
Glide和Govendor安装和使用
查看>>
Java全角、半角字符的关系以及转换
查看>>
前端项目课程3 jquery1.8.3到1.11.1有了哪些新改变
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2025-01-12 00:52:43   当前IP: 18.118.205.123   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我