⑨求助 95pts WA on #2
查看原帖
⑨求助 95pts WA on #2
254315
Larry76楼主2023/5/22 18:55

源代码:

// clang-format off
//                                                     /*[*/#include<stdio.h>//
//                         #include<stdlib.h>//]++++[->++[->+>++++<<]<][(c)2023]
//                        #ifndef                                           e//[o
//                       #include<string.h>//]![misaka.c,size=3808,crc=d0ec3b36][
//                      #define e                                           0x1//
//                     typedef struct{int d,b,o,P;char*q,*p;}f;int p,q,d,b,_=0//|
//                  #include __FILE__//]>>>[->+>++<<]<[-<<+>>>++<]>>+MISAKA*IMOUTO
//                #undef e//[->[-<<+<+<+>>>>]<<<<<++[->>+>>>+<<<<<]>+>+++>+++[>]]b
//             #define e(c)/**/if((_!=__LINE__?(_=__LINE__):0)){c;}//[20002,+[-.+]
//            ,O,i=0,Q=sizeof(f);static f*P;static FILE*t;static const char*o[]={//
//          "\n\40\"8oCan\40not\40open %s\n\0aaFbfeccdeaEbgecbbcda6bcedd#e(bbed$bbd",
//        "a6bgcdbbccd#ead$c%bcdea7bccde*b$eebbdda9bsdbeccdbbecdcbbcceed#eaa&bae$cbe",
//       "e&cbdd$eldbdeedbbdede)bdcdea&bbde1bedbbcc&b#ccdee&bdcdea'bbcd)e'bad(bae&bccd",
//      "e&bbda1bdcdee$bbce#b$c&bdedcd%ecdca4bhcdeebbcd#e$b#ecdcc$bccda7bbcc#e#d%c*bbda",
//     ">bad/bbda"};static int S(){return(o[p][q]);}static/**/int/**/Z=0  ;void/**/z(int//
//    l){if(/**/Z-l){Z=l;q++;if(p<b*5&&!S()){p+=b;q=0;}}}int main(int I,    /**/char**l){//
//   d=sizeof(f*);if(1<(O=_)){b=((sizeof(o)/sizeof(char*))-1)/4;q=22; p=     0;while(p<b*5){
//  /*<*/if(Z-1){d=S()>96;i=S()-(d?96:32) ;q++;if(p<b*5&&!S()){p+=b;  q=      0;}Z=1;}/*[[*/
//  while(i){_=o[0][S()-97];I=_-10?b:1;   for( ;I--;)putchar(_ );if   (!      --i||d)z(~i );}
// if(p==b*5&&O){p-=b;O--;}}return 0U;   }if(! (P=( f*)calloc /*]*/  (Q        ,I)))return 1;
// {;}for(_=p=1;p<I;p++){e(q=1);while    (q<   p&&  strcmp(  l[p     ]         ,l[(q)]))++  q;
// t=stdin;if(q<p){(void)memcpy/* "      */    (&P  [p],&P   [q     ]          ,Q);continue ;}
//if(strcmp(l[p],"-")){t=fopen(l         [     p]   ,"rb"   )                  ;if(!t ){{;}  ;
//printf(05+*o,l[p ]);return+1;                      {;}                       }}_=b= 1<<16   ;
//*&O=5;do{if(!(P[p].q=realloc   (P[p].q,(P[p].P     +=       b)+1))){return   01;}O   &=72   /
//6/*][*/;P[p].o+=d=fread(P[p]      .q       +P[     p           ].       o,  1,b,t)   ;}//
// while(d==b)      ;P [p].q[       P[       p]                  .o       ]=  012;d    =0;
// e(fclose(t        )  );P         [p]      .p                  =P[      p]  .q;if    (O)
// {for(;d<P[            p]          .o     ;d=                   q+     1)    {q=     d;
//  while(q<P[                        p].o&&P[                    p].q[q]-     10     ){
//  q++;}b=q-d;                         _=P                         [p].        d     ;
//  if(b>_){/*]b                                                                */
//   P[p].d=b;}{;                                                                }
//   #undef/*pqdz'.*/  e//                                                      ;
//   #define/*s8qdb]*/e/**/0                                                   //
//   //<<.<<.----.>.<<.>++.++<                                              .[>]
//   /*P[*/P[p].b++;continue;}}}t=                                       stdout;
//  for (p=1;p<I;p++){/**/if(P[p].b>i                               ){i=P[p].b;}}
// if  (O){for(p=0;p<i;p++){q=0;/*[*/while(I               >++q){_=P[q].p-P[q ].q;
//b=   0;if(_<P[q ].o){while(012-*P[q].p)     {putchar(*(P[q].p++));b++;}P[q]. p++;
//}   ;while (P[  q].d>b++)putchar(040);}             putchar(10);}return 0;}p   =1;
//   for(;   p<I   ;p++)fwrite(P[p] .q,P[              p].o,1,t);return 0 ;}//
//  #/*]     ]<.    [-]<[-]<[- ]<[    -]<               [-  ]<;*/elif  e    //b
// |(1        <<     ( __LINE__        /*               >>   `*//45))  |     01U
//             #                       /*               */     endif            //
// clang-format on

#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << ' ' << x << endl;
#define int long long
typedef pair<int, int> pii;

namespace Larry76 {

const int MAX_SIZE = 6e6;
const int INF = 0x7f7f7f7f7f7f7f7fll;
const double eps = 1e-9;
const int MOD = 1e9 + 7;

#define mul(a, b) (((a) % MOD * ((b) % MOD)) % MOD)
#define minus(a, b)          \
    ((((a) - (b)) < 0)       \
         ? ((a) - (b) + MOD) \
         : ((((a) - (b)) >= MOD) ? ((a) - (b)-MOD) : ((a) - (b))))
#define add(a, b) (((a) + (b) >= MOD) ? ((a) + (b)-MOD) : ((a) + (b)))
#define inv(x) (fastpow(x, MOD - 2))

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}

int fastpow(int base, int index) {
    int ans = 1;
    while (index) {
        if (index & 1) ans = mul(ans, base);
        base = mul(base, base);
        index >>= 1;
    }
    return ans;
}

inline int gcd(int A, int B) {
    int C;
    while (B) C = B, B = A % B, A = C;
    return A;
}

int exgcd(int A, int B, int &X, int &Y) {
    if (B == 0) {
        X = 1, Y = 0;
        return A;
    }
    int res = exgcd(B, A % B, X, Y);
    int temp = Y;
    Y = X - A / B * Y;
    X = temp;
    return res;
}

///////////// Start Coding //////////////

#undef add

int head[MAX_SIZE];
int Next[MAX_SIZE];
int ver[MAX_SIZE];
int edge[MAX_SIZE];
int tot = 1;
void add(int u, int v, int c = 0) {
    ver[++tot] = v;
    edge[tot] = c;
    Next[tot] = head[u];
    head[u] = tot;
}

const int MAX_VERTEX = 6e5;
int d[MAX_VERTEX];
bitset<MAX_VERTEX> vis;
bool SPFA(int s) {
    memset(d, 0x7f, sizeof(d));
    queue<int> q;
    q.push(s);
    d[s] = 0;
    vis[s] = 1;
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (d[v] > d[u] + edge[i]) {
                d[v] = d[u] + edge[i];
                if (!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
        vis[u] = 0;
    }
    return true;
}

int n, l, r;
int a[20];

void main() {
    n = read();
    l = read();
    r = read();
    int x = INF;
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        x = min(x, a[i]);
    }
    for (int i = 0; i < x; ++i) {
        for (int j = 1; j <= n; j++) {
            add(i, (i + a[j]) % x, (i + a[j]) / x);
        }
    }
    SPFA(0);
    int ans = 0;
    for (int i = 0; i < x; i++) {
        if (d[i] * x + i <= r) {
            int L = max(d[i] * x + i, l);
            int R = r;
            if (L / x < R / x) {
                ans += R / x - L / x - 1;
                if (L <= L / x * x + i && L / x * x + i <= R) ++ans;
                if (L <= R / x * x + i && R / x * x + i <= R) ++ans;
            } else if (L <= L / x * x + i && L / x * x + i <= R) {
                ++ans;
            }
        }
    }
    printf("%lld\n", ans);
    return void();
}

}  // namespace Larry76
signed main() {
    Larry76::main();
    return (0 ^ 0);
}

提前感谢各位大佬了/bx

2023/5/22 18:55
加载中...