• 2022“杭电杯”中国大学生算法设计超级联赛（4）D、F、G、K

    Link with Equilateral Triangle

    d

    AC代码：

    d

    BIT Subway

    阅读理解题，注意有可能从小于100直接过渡到200+，这个题答案验证是字符串类型，注意只能保留三位小数

    AC代码：

    1. #include 
    2. #define rep(i,a,n) for(int i=a;i
    3. using namespace std;
    4. using LL = long long;
    5.  
    6. void Solve() {
    7.     int n;
    8.     cin >> n;
    9.     vector<double> a(n);
    10.     for (int i = 0; i < n; i++) {
    11.         scanf("%lf", &a[i]);
    12.     }
    13.     double ans = 0.0;
    14.     double sum = 0.0;
    15.     bool ok = false;
    16.     bool ok1 = false;
    17.     for (int i = 0; i < n; i++) {
    18.         if (sum >= 100 && sum < 200) {
    19.             sum += a[i] * 0.8;
    20.         }
    21.         else if (sum >= 200) {
    22.             sum += a[i] * 0.5;
    23.         }
    24.         else {
    25.             sum += a[i];
    26.         }
    27.         if (!ok) {
    28.             if (ans + a[i] >= 100 && (a[i] - (100 - ans)) * 0.8 + 100.0 >= 200) {
    29.                 double c = 100 - ans;
    30.                 ans = 100.0;
    31.                 a[i] = 1.0 * a[i] - c;
    32.                 double d = (200.0 - ans);
    33.                 double l = 0.0, r = a[i];
    34.                 for (int i = 0; i < 50; i++) {
    35.                     double mid = (l + r) / 2;
    36.                     if (mid * 0.8 > d) {
    37.                         r = mid;
    38.                     }
    39.                     else {
    40.                         l = mid;
    41.                     }
    42.                 }
    43.                 ans = 200.0;
    44.                 ans += 1.0 * (a[i] * 1.0 - l) * 0.5;
    45.                 ok = true;
    46.                 ok1 = true;
    47.                 continue;
    48.             }
    49.             if (ans + a[i] >= 100) {
    50.                 double c = ans + a[i] - 100;
    51.                 ans = 100.0;
    52.                 ans += 1.0 * c * 0.8;
    53.                 ok = true;
    54.             }
    55.             else {
    56.                 ans += a[i];
    57.             }
    58.         }
    59.         else {
    60.             if (ans + 1.0 * a[i] * 0.8 >= 200.0 && !ok1) {
    61.                 double d = (200.0 - ans);
    62.                 double l = 0.0, r = 1.0 * a[i];
    63.                 for (int i = 0; i < 50; i++) {
    64.                     double mid = (l + r) / 2;
    65.                     if (mid * 0.8 > d) {
    66.                         r = mid;
    67.                     }
    68.                     else {
    69.                         l = mid;
    70.                     }
    71.                 }
    72.                 ans = 200.0;
    73.                 ans += 1.0 * (a[i] * 1.0 - l) * 0.5;
    74.                 ok1 = true;
    75.             }
    76.             else if (ok1 && ans >= 200) {
    77.                 ans += 0.5 * a[i];
    78.             }
    79.             else {
    80.                 ans += 0.8 * a[i];
    81.             }
    82.         }
    83.     }
    84.     printf("%.3lf %.3lf\n", ans, sum);
    85. }
    86.  
    87. int main() {
    88.  
    89.     int T;
    90.     scanf("%d", &T);
    91.     rep (i, 0, T) {
    92.         Solve();
    93.     }
    94.  
    95.     return 0;
    96. }

    Climb Stairs

    因为只能向上跳k步向下跳1步，走过的楼层不能再走，而且要杀死所有怪兽，只能一段一段考虑，否则下面一定有漏掉的怪兽没有打，所以每次攻击力不够了，我们应从能跳到的最远处（或最后一个怪兽的位置，否则RE）且能够打死的怪兽往后枚举，这样保证都能杀死的同时还可以增加攻击力，如果又遇上打不过的，就将攻击力初始化再重复上述操作，直到遇上最开始打不过的怪兽，如果还打不过，那就真打不过了，否则跳到开始增加攻击力的楼层的下一个位置，这个位置要么是跳不到的最近的地方，要么是最初攻击力打不过的地方

    这样的暴力竟然比他的标程线段树还快，时间复杂度确实没什么问题

     

    AC代码：

    1. #include 
    2. #define rep(i,a,n) for(int i=a;i
    3. using namespace std;
    4. using LL = long long;
    5. const int mod = 1e9 + 7;
    6.  
    7. void Solve() {
    8.     LL n, fi, k;
    9.     cin >> n >> fi >> k;
    10.     vector a(n + 1);
    11.     for (int i = 1; i <= n; i++) {
    12.         cin >> a[i];
    13.     }
    14.     for (int i = 1; i <= n; i++) {
    15.         if (a[i] > fi) {
    16.             int j = i + k - 1;
    17.             if (i + k - 1 > n) {
    18.                 j = n;
    19.             }
    20.             int l = j;
    21.             LL start = fi;
    22.             bool ok = false;
    23.             for (int z = j; z >= i; z--) {
    24.                 if (fi >= a[z]) {
    25.                     fi += a[z];
    26.                     if (z == i) {
    27.                         ok = true;
    28.                         break;
    29.                     }
    30.                 }
    31.                 else {
    32.                     fi = start;
    33.                     l = z - 1;
    34.                 }
    35.             }
    36.             if (ok) {
    37.                 i = l + 1;
    38.             }
    39.             else {
    40.                 cout << "NO\n";
    41.                 return;
    42.             }
    43.         }
    44.         else {
    45.             fi += a[i];
    46.         }
    47.     }
    48.     cout << "YES\n";
    49. }
    50.  
    51. int main() {
    52.     ios::sync_with_stdio(false);
    53.     cin.tie(nullptr);
    54.  
    55.     int T;
    56.     cin >> T;
    57.     rep (i, 0, T) {
    58.         Solve();
    59.     }
    60.  
    61.     return 0;
    62. }

    标程：

    1. #include
    2. #define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
    3. #define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
    4. #define ren for(int i=fst[x];i;i=nxt[i])
    5. #define Fill(a,x) memset(a,x,sizeof(a))
    6. using namespace std;
    7. typedef long long ll;
    8. typedef double db;
    9. typedef long double ld;
    10. typedef unsigned long long ull;
    11. typedef vector<int> vi;
    12. typedef pair<int,int> pii;
    13. const int inf=2139062143;
    14. const int MOD=998244353;
    15. const int MAXN=200100;
    16. inline int read()
    17. {
    18.     int x=0,f=1;char ch=getchar();
    19.     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    20.     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    21.     return x*f;
    22. }
    23. inline ll readll()
    24. {
    25.     ll x=0,f=1;char ch=getchar();
    26.     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    27.     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    28.     return x*f;
    29. }
    30. namespace CALC
    31. {
    32.     inline int pls(int a,int b){return a+b>=MOD?a+b-MOD:a+b;}
    33.     inline int mns(int a,int b){return a-b<0?a-b+MOD:a-b;}
    34.     inline int mul(int a,int b){return (1LL*a*b)%MOD;}
    35.     inline void inc(int &a,int b){a=pls(a,b);}
    36.     inline void dec(int &a,int b){a=mns(a,b);}
    37.     inline void tms(int &a,int b){a=mul(a,b);}
    38.     inline int qp(int x,int t,int res=1)
    39.         {for(;t;t>>=1,x=mul(x,x)) if(t&1) res=mul(res,x);return res;}
    40.     inline int Inv(int x){return qp(x,MOD-2);}
    41. }
    42. using namespace CALC;
    43. int n,a[MAXN],k,las,cur,l,r;
    44. pairint> q[MAXN];
    45. ll sum[MAXN],f[MAXN],mxf[MAXN];
    46. ll mn[MAXN<<2];
    47. void build(int k,int l,int r)
    48. {
    49.     if(l==r) {mn[k]=f[l];return ;}int mid=l+r>>1;
    50.     build(k<<1,l,mid);build(k<<1|1,mid+1,r);
    51.     mn[k]=min(mn[k<<1],mn[k<<1|1]);
    52. }
    53. int res=inf;
    54. void query(int k,int l,int r,int a,int b,int w)
    55. {
    56.     if(a<=l&&r<=b)
    57.     {
    58.         if(mn[k]>w||res!=inf) return ;
    59.         if(l==r) {res=l;return ;}int mid=l+r>>1;
    60.         if(mn[k<<1]<=w) query(k<<1,l,mid,a,b,w);
    61.         else if(mn[k<<1|1]<=w) query(k<<1|1,mid+1,r,a,b,w);
    62.         return ;
    63.     }
    64.     int mid=l+r>>1;
    65.     if(a<=mid) query(k<<1,l,mid,a,b,w);
    66.     if(b>mid) query(k<<1|1,mid+1,r,a,b,w);
    67. }
    68. int solve()
    69. {
    70.     n=read(),a[0]=sum[0]=read(),k=min(read(),n);
    71.     rep(i,1,n) a[i]=read(),sum[i]=sum[i-1]+a[i];
    72.     f[0]=sum[0]<<1;rep(i,1,n) f[i]=max(sum[i]+a[i],f[i-1]);
    73.     rep(i,0,n) f[i]=f[i]-sum[i];
    74.     //rep(i,0,n) cout<
    75.     build(1,1,n);
    76.     las=-1,cur=0;
    77.     while(cur!=n)
    78.     {
    79.         res=inf;
    80.         query(1,1,n,cur+1,min(las+k+1,n),sum[cur]);
    81.         //cout<
    82.         if(res==inf) return 0;
    83.         las=cur,cur=res;
    84.     }
    85.     return 1;
    86. }
    87. int main()
    88. {
    89.     rep(T,1,read()) puts(solve()?"YES":"NO");
    90. }

    Link is as bear

    线性基板板题，从这 个数里任取一些数异或起来的方案，都是可以构造出对应的操作来 做到的，问题完全等价于给n个数，从中选一些数，使得这些数的异或和最大。

    AC代码：

    1. #include 
    2. #define rep(i,a,n) for(int i=a;i
    3. using namespace std;
    4. using LL = long long;
    5. const int mod = 1e9 + 7;
    6.  
    7.  
    8. void Solve() {
    9.     int n;
    10.     cin >> n;
    11.     vector a(n);
    12.     for (int i = 0; i < n; i++) {
    13.         cin >> a[i];
    14.     }
    15.     int k = 0;
    16.     for (int i = 62; i >= 0; i--) {
    17.         for (int j = k; j < n; j++) {
    18.             if (a[j] >> i & 1) {
    19.                 swap(a[j], a[k]);
    20.                 break;
    21.             }
    22.         }
    23.         if (!(a[k] >> i & 1)) {
    24.             continue;
    25.         }
    26.         for (int j = 0; j < n; j++) {
    27.             if (j != k && (a[j] >> i & 1)) {
    28.                 a[j] ^= a[k];
    29.             }
    30.         }
    31.         k++;
    32.         if (k == n) {
    33.             break;
    34.         }
    35.     }
    36.     LL ans = 0;
    37.     for (int i = 0; i < k; i++) {
    38.         ans ^= a[i];
    39.     }
    40.     cout << ans << '\n';
    41. }
    42.  
    43. int main() {
    44.     ios::sync_with_stdio(false);
    45.     cin.tie(nullptr);
    46.  
    47.     int T;
    48.     cin >> T;
    49.     rep (i, 0, T) {
    50.         Solve();
    51.     }
    52.  
    53.     return 0;
    54. }

  • 相关阅读:
    Java面试（JVM篇）——JVM 面试题合集 & 深入理解JVM虚拟机
    uniapp如何在页面中只展示一条随机数据
    Playwright+Python+Pytest：基础方法二次封装简化及链式调用
    Hadoop--03---HDFS_01----概述
    网上期货开户高效方便简单
    基于JavaWeb的家庭食谱管理系统设计与实现
    C#控件开发错误解决记录
    Jmeter安装(快速入门)
    EN 14384立柱式消防栓—CE认证
    原生Javascript（数组操作方法总结）-更新
  • 原文地址：https://blog.csdn.net/eyuhaobanga/article/details/126117829