2019的hdu暑假作业（欢迎纠错）-白红宇

2019的hdu暑假作业（欢迎纠错）

阅读量：4975 次

发布时间：2019-06-12

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

6月26日

被1226烦得头都大了，从下午断断续续调到晚。最后数组开小给报个Tle看了半天没看出来...

6月30日

每日补题，进度停滞中...

7月10日

第一阶段结束...不做鸽子了不做鸽子了。

7月11日

被卡了....还没题解....生命--。

7月21日

达到40题之后已经咸鱼了。随缘做做。

hdu1219

遍历计数。

1 #include
      
        2 #define QAQ 0 3  4 using namespace std; 5  6 char a[100010]; 7 int cnt[200]; 8 int main(){ 9     while(cin.getline(a,100005)){10         memset(cnt,0,sizeof(cnt));11         int l=strlen(a);12         for(int i=0;i

hdu 1219

hdu1220

总对数减去相邻的对数。相邻的对数分类为顶点、棱、面、体内的小正方体，分别对应邻接3、4、5、6个，每对算了两次。

1 #include
      
        2 #define QAQ 0 3  4 using namespace std; 5 typedef long long ll; 6  7 ll n; 8  9 int main(){10     while(scanf("%lld",&n)!=EOF){11         if(n==1){12             printf("%lld\n",0);13             continue;14         }15         ll sum=n*n*n*(n*n*n-1)/2,cnt;16         cnt=8*3 + 12*(n-2)*4 + 6*(n-2)*(n-2)*5 + (n-2)*(n-2)*(n-2)*6;17         printf("%lld\n",sum-cnt/2);18     }19     return QAQ;20 }

hdu 1220

hdu1221

最大值一定到在圆心到矩形四个顶点里，最小值除了到顶点距离外，再判一下圆心到四条边距离。

1 #include
      
        2 #define QAQ 0 3  4 using namespace std; 5 typedef long long ll; 6 const double eps=1e-7; 7  8 double x,y,r,a1,b1,a2,b2,a3,b3,a4,b4,maxi,mini; 9 ll T;10 11 double dis(double x1, double y1, double x2, double y2){12     return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );13 }14 15 int main(){16     scanf("%lld",&T);17     while(T--){18         scanf("%lf%lf%lf%lf%lf%lf%lf",&x,&y,&r,&a1,&b1,&a2,&b2);19         a3=a1; b3=b2; a4=a2; b4=b1;20         double l1=dis(x,y,a1,b1),l2=dis(x,y,a2,b2),21         l3=dis(x,y,a3,b3),l4=dis(x,y,a4,b4);22         23         maxi=max( max(l1,l2) , max(l3,l4) );24         mini=min( min(l1,l2) , min(l3,l4) );25         26         if(x>a1 && x
       
        b1 && y
        
         =r){35             printf("YES");36         }37         else printf("NO");38         printf("\n");39     }40     return QAQ;41 }

hdu 1221

hdu1222

如果m和n的最大公约数不为1，则一定有安全位置。

1 #include
      
        2 #define QAQ 0 3  4 using namespace std; 5  6 int T,m,n; 7  8 int gcd(int a,int b){ 9     return b==0?a:gcd(b,a%b);10 }11 12 int main(){13     scanf("%d",&T);14     while(T--){15         scanf("%d%d",&m,&n);16         if(gcd(m,n)!=1) printf("YES");17         else printf("NO");18         printf("\n");19     }20     return QAQ;21 }

hdu 1222

hdu1223

有等号连接的为一个块，dp[i][j]表示i个字母有j个块。对于i-1个字母分两类：1.原有j块，即添加等号，显然和每个块相等为一种，共j种；2.原有j-1块，即添加小于号，j-1个块有j个空位可以放入，也为j种。所以dp[i][j]=dp[i-1][j]*j+dp[i-1]][j-1]*j。

本题没有mod，要用大数。感谢颜神的模板支援o(*￣▽￣*)ブ。

1 #include
      
         2 #define QAQ 0  3   4 using namespace std;  5 typedef long long ll;  6   7 int T,n;  8   9 const int base = 1000000000; 10 const int base_digits = 9; 11  12 struct Bigint { 13     vector
       
         z; 14     int sign; 15  16     Bigint() : 17         sign(1) { 18     } 19  20     Bigint(long long v) { 21         *this = v; 22     } 23  24     Bigint(const string &s) { 25         read(s); 26     } 27  28     void operator=(const Bigint &v) { 29         sign = v.sign; 30         z = v.z; 31     } 32  33     void operator=(long long v) { 34         sign = 1; 35         if (v < 0) 36             sign = -1, v = -v; 37         z.clear(); 38         for (; v > 0; v = v / base) 39             z.push_back(v % base); 40     } 41  42     Bigint operator+(const Bigint &v) const { 43         if (sign == v.sign) { 44             Bigint res = v; 45  46             for (int i = 0, carry = 0; i < (int) max(z.size(), v.z.size()) || carry; ++i) { 47                 if (i == (int) res.z.size()) 48                     res.z.push_back(0); 49                 res.z[i] += carry + (i < (int) z.size() ? z[i] : 0); 50                 carry = res.z[i] >= base; 51                 if (carry) 52                     res.z[i] -= base; 53             } 54             return res; 55         } 56         return *this - (-v); 57     } 58  59     Bigint operator-(const Bigint &v) const { 60         if (sign == v.sign) { 61             if (abs() >= v.abs()) { 62                 Bigint res = *this; 63                 for (int i = 0, carry = 0; i < (int) v.z.size() || carry; ++i) { 64                     res.z[i] -= carry + (i < (int) v.z.size() ? v.z[i] : 0); 65                     carry = res.z[i] < 0; 66                     if (carry) 67                         res.z[i] += base; 68                 } 69                 res.trim(); 70                 return res; 71             } 72             return -(v - *this); 73         } 74         return *this + (-v); 75     } 76  77     void operator*=(int v) { 78         if (v < 0) 79             sign = -sign, v = -v; 80         for (int i = 0, carry = 0; i < (int) z.size() || carry; ++i) { 81             if (i == (int) z.size()) 82                 z.push_back(0); 83             long long cur = z[i] * (long long) v + carry; 84             carry = (int) (cur / base); 85             z[i] = (int) (cur % base); 86             //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base)); 87         } 88         trim(); 89     } 90  91     Bigint operator*(int v) const { 92         Bigint res = *this; 93         res *= v; 94         return res; 95     } 96  97     friend pair
        
          divmod(const Bigint &a1, const Bigint &b1) { 98         int norm = base / (b1.z.back() + 1); 99         Bigint a = a1.abs() * norm;100         Bigint b = b1.abs() * norm;101         Bigint q, r;102         q.z.resize(a.z.size());103 104         for (int i = a.z.size() - 1; i >= 0; i--) {105             r *= base;106             r += a.z[i];107             int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : 0;108             int s2 = b.z.size() - 1 < r.z.size() ? r.z[b.z.size() - 1] : 0;109             int d = ((long long) s1 * base + s2) / b.z.back();110             r -= b * d;111             while (r < 0)112                 r += b, --d;113             q.z[i] = d;114         }115 116         q.sign = a1.sign * b1.sign;117         r.sign = a1.sign;118         q.trim();119         r.trim();120         return make_pair(q, r / norm);121     }122 123     friend Bigint sqrt(const Bigint &a1) {124         Bigint a = a1;125         while (a.z.empty() || a.z.size() % 2 == 1)126             a.z.push_back(0);127 128         int n = a.z.size();129 130         int firstDigit = (int) sqrt((double) a.z[n - 1] * base + a.z[n - 2]);131         int norm = base / (firstDigit + 1);132         a *= norm;133         a *= norm;134         while (a.z.empty() || a.z.size() % 2 == 1)135             a.z.push_back(0);136 137         Bigint r = (long long) a.z[n - 1] * base + a.z[n - 2];138         firstDigit = (int) sqrt((double) a.z[n - 1] * base + a.z[n - 2]);139         int q = firstDigit;140         Bigint res;141 142         for(int j = n / 2 - 1; j >= 0; j--) {143             for(; ; --q) {144                 Bigint r1 = (r - (res * 2 * base + q) * q) * base * base + (j > 0 ? (long long) a.z[2 * j - 1] * base + a.z[2 * j - 2] : 0);145                 if (r1 >= 0) {146                     r = r1;147                     break;148                 }149             }150             res *= base;151             res += q;152 153             if (j > 0) {154                 int d1 = res.z.size() + 2 < r.z.size() ? r.z[res.z.size() + 2] : 0;155                 int d2 = res.z.size() + 1 < r.z.size() ? r.z[res.z.size() + 1] : 0;156                 int d3 = res.z.size() < r.z.size() ? r.z[res.z.size()] : 0;157                 q = ((long long) d1 * base * base + (long long) d2 * base + d3) / (firstDigit * 2);158             }159         }160 161         res.trim();162         return res / norm;163     }164 165     Bigint operator/(const Bigint &v) const {166         return divmod(*this, v).first;167     }168 169     Bigint operator%(const Bigint &v) const {170         return divmod(*this, v).second;171     }172 173     void operator/=(int v) {174         if (v < 0)175             sign = -sign, v = -v;176         for (int i = (int) z.size() - 1, rem = 0; i >= 0; --i) {177             long long cur = z[i] + rem * (long long) base;178             z[i] = (int) (cur / v);179             rem = (int) (cur % v);180         }181         trim();182     }183 184     Bigint operator/(int v) const {185         Bigint res = *this;186         res /= v;187         return res;188     }189 190     int operator%(int v) const {191         if (v < 0)192             v = -v;193         int m = 0;194         for (int i = z.size() - 1; i >= 0; --i)195             m = (z[i] + m * (long long) base) % v;196         return m * sign;197     }198 199     void operator+=(const Bigint &v) {200         *this = *this + v;201     }202     void operator-=(const Bigint &v) {203         *this = *this - v;204     }205     void operator*=(const Bigint &v) {206         *this = *this * v;207     }208     void operator/=(const Bigint &v) {209         *this = *this / v;210     }211 212     bool operator<(const Bigint &v) const {213         if (sign != v.sign)214             return sign < v.sign;215         if (z.size() != v.z.size())216             return z.size() * sign < v.z.size() * v.sign;217         for (int i = z.size() - 1; i >= 0; i--)218             if (z[i] != v.z[i])219                 return z[i] * sign < v.z[i] * sign;220         return false;221     }222 223     bool operator>(const Bigint &v) const {224         return v < *this;225     }226     bool operator<=(const Bigint &v) const {227         return !(v < *this);228     }229     bool operator>=(const Bigint &v) const {230         return !(*this < v);231     }232     bool operator==(const Bigint &v) const {233         return !(*this < v) && !(v < *this);234     }235     bool operator!=(const Bigint &v) const {236         return *this < v || v < *this;237     }238 239     void trim() {240         while (!z.empty() && z.back() == 0)241             z.pop_back();242         if (z.empty())243             sign = 1;244     }245 246     bool isZero() const {247         return z.empty() || (z.size() == 1 && !z[0]);248     }249 250     Bigint operator-() const {251         Bigint res = *this;252         res.sign = -sign;253         return res;254     }255 256     Bigint abs() const {257         Bigint res = *this;258         res.sign *= res.sign;259         return res;260     }261 262     long long longValue() const {263         long long res = 0;264         for (int i = z.size() - 1; i >= 0; i--)265             res = res * base + z[i];266         return res * sign;267     }268 269     friend Bigint gcd(const Bigint &a, const Bigint &b) {270         return b.isZero() ? a : gcd(b, a % b);271     }272     friend Bigint lcm(const Bigint &a, const Bigint &b) {273         return a / gcd(a, b) * b;274     }275 276     void read(const string &s) {277         sign = 1;278         z.clear();279         int pos = 0;280         while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {281             if (s[pos] == '-')282                 sign = -sign;283             ++pos;284         }285         for (int i = s.size() - 1; i >= pos; i -= base_digits) {286             int x = 0;287             for (int j = max(pos, i - base_digits + 1); j <= i; j++)288                 x = x * 10 + s[j] - '0';289             z.push_back(x);290         }291         trim();292     }293 294     friend istream& operator>>(istream &stream, Bigint &v) {295         string s;296         stream >> s;297         v.read(s);298         return stream;299     }300 301     friend ostream& operator<<(ostream &stream, const Bigint &v) {302         if (v.sign == -1)303             stream << '-';304         stream << (v.z.empty() ? 0 : v.z.back());305         for (int i = (int) v.z.size() - 2; i >= 0; --i)306             stream << setw(base_digits) << setfill('0') << v.z[i];307         return stream;308     }309 310     static vector
         
           convert_base(const vector
          
            &a, int old_digits, int new_digits) {311         vector
           
             p(max(old_digits, new_digits) + 1);312 p[0] = 1;313 for (int i = 1; i < (int) p.size(); i++)314 p[i] = p[i - 1] * 10;315 vector
            
              res;316 long long cur = 0;317 int cur_digits = 0;318 for (int i = 0; i < (int) a.size(); i++) {319 cur += a[i] * p[cur_digits];320 cur_digits += old_digits;321 while (cur_digits >= new_digits) {322 res.push_back(int(cur % p[new_digits]));323 cur /= p[new_digits];324 cur_digits -= new_digits;325 }326 }327 res.push_back((int) cur);328 while (!res.empty() && res.back() == 0)329 res.pop_back();330 return res;331 }332 333 typedef vector
             
               vll;334 335 static vll karatsubaMultiply(const vll &a, const vll &b) {336 int n = a.size();337 vll res(n + n);338 if (n <= 32) {339 for (int i = 0; i < n; i++)340 for (int j = 0; j < n; j++)341 res[i + j] += a[i] * b[j];342 return res;343 }344 345 int k = n >> 1;346 vll a1(a.begin(), a.begin() + k);347 vll a2(a.begin() + k, a.end());348 vll b1(b.begin(), b.begin() + k);349 vll b2(b.begin() + k, b.end());350 351 vll a1b1 = karatsubaMultiply(a1, b1);352 vll a2b2 = karatsubaMultiply(a2, b2);353 354 for (int i = 0; i < k; i++)355 a2[i] += a1[i];356 for (int i = 0; i < k; i++)357 b2[i] += b1[i];358 359 vll r = karatsubaMultiply(a2, b2);360 for (int i = 0; i < (int) a1b1.size(); i++)361 r[i] -= a1b1[i];362 for (int i = 0; i < (int) a2b2.size(); i++)363 r[i] -= a2b2[i];364 365 for (int i = 0; i < (int) r.size(); i++)366 res[i + k] += r[i];367 for (int i = 0; i < (int) a1b1.size(); i++)368 res[i] += a1b1[i];369 for (int i = 0; i < (int) a2b2.size(); i++)370 res[i + n] += a2b2[i];371 return res;372 }373 374 Bigint operator*(const Bigint &v) const {375 vector
              
                a6 = convert_base(this->z, base_digits, 6);376 vector
               
                 b6 = convert_base(v.z, base_digits, 6);377 vll a(a6.begin(), a6.end());378 vll b(b6.begin(), b6.end());379 while (a.size() < b.size())380 a.push_back(0);381 while (b.size() < a.size())382 b.push_back(0);383 while (a.size() & (a.size() - 1))384 a.push_back(0), b.push_back(0);385 vll c = karatsubaMultiply(a, b);386 Bigint res;387 res.sign = sign * v.sign;388 for (int i = 0, carry = 0; i < (int) c.size(); i++) {389 long long cur = c[i] + carry;390 res.z.push_back((int) (cur % 1000000));391 carry = (int) (cur / 1000000);392 }393 res.z = convert_base(res.z, 6, base_digits);394 res.trim();395 return res;396 }397 }dp[60][60],sum[60];398 399 int main(){400 scanf("%d",&T);401 for(int i=1;i<=50;i++){402 dp[i][1]=1;403 }404 for(int i=2;i<=50;i++){405 for(int j=2;j<=i;j++){406 dp[i][j]=dp[i-1][j]*j + dp[i-1][j-1]*j;407 }408 }409 for(int i=1;i<=50;i++){410 for(int j=1;j<=i;j++){411 sum[i]=sum[i]+dp[i][j];412 }413 }414 while(T--){415 scanf("%d",&n);416 cout<
                
                 <<'\n';417 }418 return QAQ;419 }

hdu 1223

hdu1224

数据很小，dfs一遍，顺带记录一下走的路线。

1 #include
      
        2 #define QAQ 0 3  4 using namespace std; 5  6 int T,n,cas,maxi,m,u,v,a[102]; 7 vector
       
        ve[102],tmp,ans; 8  9 void dfs(int x,int t){10     if(x==n+1){11         if(t>maxi){12             maxi=t;13             ans.clear();14             ans=tmp;15         }16         return;17     }18     for(auto y:ve[x]){19         tmp.push_back(x);20         dfs(y,t+a[y]);21         tmp.pop_back();22     }23 }24 25 int main(){26     scanf("%d",&T);27     while(T--){28         maxi=-1;29         tmp.clear(); ans.clear();30         scanf("%d",&n);31         for(int i=1;i<=n;i++){32             scanf("%d",&a[i]);33             ve[i].clear();34         }35         a[n+1]=a[1];36         scanf("%d",&m);37         for(int i=1;i<=m;i++){38             scanf("%d%d",&u,&v);39             ve[u].push_back(v);40         }41         dfs(1,a[1]);42         cas++;43         printf("CASE %d#\npoints : %d\ncircuit : ",cas,maxi);44         for(auto x:ans){45             printf("%d->",x);46         }47         printf("1\n");48         if(T) printf("\n");49     }50     return QAQ;51 }

hdu 1224

hdu1225

按题意模拟，用map计数，排序输出。

1 #include
      
        2 #define QAQ 0 3 #define miaojie 4 #ifdef miaojie 5   #define dbg(args...) do {cout << #args << " : "; err(args);} while (0) 6 void err() {std::cout << std::endl;} 7 template
       
         8 void err(T a, Args...args){std::cout << a << ' '; err(args...);} 9 #else10   #define dbg(...)11 #endif12 13 using namespace std;14 15 struct node{16     string ss;17     int r,r2,r3;18     bool operator <(const node a) const{19         if(r==a.r){20             if(r2==a.r2){21                 if(r3==a.r3){22                     return ss
        
         a.r3;25             }26             return r2>a.r2;27         }28         return r>a.r;29     }30 };31 32 int n,a,b;33 char c;34 string s1,s2,s3;35 map
         
          m,m2,m3;36 set
          
           s;37 38 int main(){39     while(cin>>n){40         m.clear(); m2.clear(); m3.clear(); s.clear();41         for(int i=1;i<=n*(n-1);i++){42             cin>>s1>>s2>>s3;43             cin>>a>>c>>b;44             s.insert(s1); s.insert(s3);45             m2[s1]=m2[s1]+a-b;46             m2[s3]=m2[s3]+b-a;47             m3[s1]+=a;48             m3[s3]+=b;49             if(a>b){50                 m[s1]+=3;51             }52             else if(a==b){53                 m[s1]++;54                 m[s3]++;55             }56             else{57                 m[s3]+=3;58             }    59         }60         61         node ans[n];62         int p=0;63         for(auto x:s){64             ans[p].r=m[x];65             ans[p].r2=m2[x];66             ans[p].r3=m3[x];67             ans[p].ss=x;68             p++;69         }70         sort(ans,ans+p);71         for(int i=0;i

hdu 1225

hdu1226

题目给了10s...从高位到低位bfs，这样保证一定从小到大，直到搜到模n为0的。模n相同的数等价，所以前面出现过的余数后面再有就不必入队了。n=0特判。

1 #include
      
        2 #define QAQ 0 3 #define miaojie1 4 #ifdef miaojie 5   #define dbg(args...) do {cout << #args << " : "; err(args);} while (0) 6 void err() {std::cout << std::endl;} 7 template
       
         8 void err(T a, Args...args){std::cout << a << ' '; err(args...);} 9 #else10   #define dbg(...)11 #endif12 13 using namespace std;14 15 int T,n,c,m;16 char ch[5];17 bool f[20],r[5005];18 19 struct node{20     int v[505],l,rr;21 };22 23 void bfs(){24     queue
        
         q;25     for(int i=1;i<=15;i++){26         if(f[i]){27             node t;28             t.v[0]=i;29             t.rr=i%n;30             if(r[t.rr]) continue;31             r[t.rr]=1;32             t.l=1;33             if(!t.rr){34                 if(i>=10){35                     printf("%c",i+55);36                 }37                 else printf("%d",i);38                 return;39             }40             q.push(t);41         }42     }43     while(!q.empty()){44         node t=q.front();45         q.pop();46         for(int i=0;i<=15;i++){47             if(f[i]){48                 node tt=t;49                 tt.rr=(tt.rr*c+i)%n;50                 tt.v[tt.l++]=i;51                 if(!tt.rr){52                     for(int j=0;j
         
          =10){54                             printf("%c",tt.v[j]+55);55                         }56                         else printf("%d",tt.v[j]);57                     }58                     dbg(tt.l);59                     return;60                 }61                 if(!r[tt.rr] && tt.l<=499){62                     r[tt.rr]=1;63                     q.push(tt);64                 }65             }66         }67     }68     printf("give me the bomb please");69 }70 71 int main(){72     scanf("%d",&T);73     while(T--){74         scanf("%d%d%d",&n,&c,&m);75         memset(f,0,sizeof(f));76         memset(r,0,sizeof(r));77         78         for(int i=1;i<=m;i++){79             scanf("%s",ch);80             if(ch[0]>='A'){81                 f[ch[0]-55]=1;82             }83             else f[ch[0]-48]=1;84         }85         if(n==0){86             if(f[0]){87                 printf("0\n");88             }89             else printf("give me the bomb please\n");90             continue;91         }92         bfs();93         printf("\n");94     }95     return QAQ;96 }

hdu 1226

hdu 1256

根据下面内圈一定是正方形推一下各个长度。题目表达的意思是竖线宽为n/6+1....读题读错了。

1 #include
      
        2 #define QAQ 0 3  4 using namespace std; 5  6 int T,n,a,b,d; 7 char c,s[4]; 8  9 void f(){10     for(int i=1;i<=d;i++){11         printf(" ");12     }13     for(int i=1;i<=b;i++){14         printf("%c",c);15     }16     printf("\n");17 }18 19 void f2(int x){20     for(int i=1;i<=x;i++){21         for(int j=1;j<=d;j++){22             printf("%c",c);23         }24         for(int j=1;j<=b;j++){25             printf(" ");26         }27         for(int j=1;j<=d;j++){28             printf("%c",c);29         }30         printf("\n");31     }32 }33 34 int main(){35     scanf("%d",&T);36     while(T--){37         scanf("%s%d",s,&n);38         c=s[0];39         a=(n-3)/2,b=(n-2)/2,d=n/6+1;40         f(); f2(a);41         f(); f2(b);42         f();43         if(T) printf("\n");44     }45     return QAQ;46 }

hdu 1256

hdu 1257

转化为求最长上升子序列。默写板子...

1 #include
      
        2 #define QAQ 0 3  4 using namespace std; 5 const int maxn=1e6+10; 6  7 int n,a[maxn],dp[maxn]; 8  9 int main(){10     while(scanf("%d",&n)!=EOF){11         int ans=-1;12         for(int i=1;i<=n;i++){13             scanf("%d",&a[i]);14             dp[i]=1;15         }16         for(int i=1;i<=n;i++){17             for(int j=1;j
       
        a[j]){19                     dp[i]=max(dp[j]+1,dp[i]);    20                 }21             }22         }23         for(int i=1;i<=n;i++){24             ans=max(ans,dp[i]);25         }26         printf("%d\n",ans);27     }28     return QAQ;29 }

hdu 1257

hdu 1258

又是快乐dfs，题目已经排好序了~

注意每次搜的时候去重，比如搜到50的时候，下一个和再下一个都是25，只能搜1次25。也就是同一层不能搜重复数，不然最后会有相同的疯狂刷屏.....

1 #include
      
        2 #define QAQ 0 3  4 using namespace std; 5  6 int t,n,cnt,sum,a[1000]; 7 vector
       
        v; 8  9 void dfs(int x){10     if(sum>t) return;11     if(sum==t){12         cnt++;13         for(int i=0;i

hdu 1258

hdu 1259

按题意模拟。

1 #include
      
        2 #define QAQ 0 3  4 using namespace std; 5  6 int n,m,x,y; 7  8 int main(){ 9     scanf("%d",&n);10     while(n--){11         string s="$ZJUTACM";12         scanf("%d",&m);13         for(int i=1;i<=m;i++){14             scanf("%d%d",&x,&y);15             swap(s[x],s[y]);16         }17         for(int i=1;i<=7;i++){18             if(s[i]=='J'){19                 printf("%d\n",i);20                 break;21             }22         }23     }24     return QAQ;25 }

hdu 1259

hdu 1260

dp[i]表示让i个人买完票的最短时间。第i个人买票要么单独买，要么和前面的人合买。

状态转移方程dp[i]=min(dp[i-1]+s[i],dp[i-2]+d[i-1])。

1 #include
      
        2 #define QAQ 0 3  4 using namespace std; 5  6 int N,k,s[2019],d[2019],dp[2019]; 7  8 int main(){ 9     scanf("%d",&N);10     while(N--){11         bool f=0;12         scanf("%d",&k);13         memset(dp,0,sizeof(dp));14         for(int i=1;i<=k;i++){15             scanf("%d",&s[i]);16         }17         for(int i=1;i<=k-1;i++){18             scanf("%d",&d[i]);19         }20         21         dp[1]=s[1];22         for(int i=2;i<=k;i++){23             dp[i]=min(dp[i-1]+s[i],dp[i-2]+d[i-1]);24         }25         int a=dp[k]/3600+8,b=dp[k]/60%60,c=dp[k]%60;26         if(a>=12){27             a-=12;28             f=1;29         }30         printf("%02d:%02d:%02d ",a,b,c);31         if(f) printf("pm\n");32         else printf("am\n");33     }34     return QAQ;35 }

hdu 1260

hdu 1261

组合数公式 sigma(a)! / sigma(a!) ，爆ll了，用大数。

1 #include
      
         2 #define QAQ 0  3   4 using namespace std;  5   6 const int base = 1000000000;  7 const int base_digits = 9;  8   9 struct Bigint { 10     vector
       
         z; 11     int sign; 12  13     Bigint() : 14         sign(1) { 15     } 16  17     Bigint(long long v) { 18         *this = v; 19     } 20  21     Bigint(const string &s) { 22         read(s); 23     } 24  25     void operator=(const Bigint &v) { 26         sign = v.sign; 27         z = v.z; 28     } 29  30     void operator=(long long v) { 31         sign = 1; 32         if (v < 0) 33             sign = -1, v = -v; 34         z.clear(); 35         for (; v > 0; v = v / base) 36             z.push_back(v % base); 37     } 38  39     Bigint operator+(const Bigint &v) const { 40         if (sign == v.sign) { 41             Bigint res = v; 42  43             for (int i = 0, carry = 0; i < (int) max(z.size(), v.z.size()) || carry; ++i) { 44                 if (i == (int) res.z.size()) 45                     res.z.push_back(0); 46                 res.z[i] += carry + (i < (int) z.size() ? z[i] : 0); 47                 carry = res.z[i] >= base; 48                 if (carry) 49                     res.z[i] -= base; 50             } 51             return res; 52         } 53         return *this - (-v); 54     } 55  56     Bigint operator-(const Bigint &v) const { 57         if (sign == v.sign) { 58             if (abs() >= v.abs()) { 59                 Bigint res = *this; 60                 for (int i = 0, carry = 0; i < (int) v.z.size() || carry; ++i) { 61                     res.z[i] -= carry + (i < (int) v.z.size() ? v.z[i] : 0); 62                     carry = res.z[i] < 0; 63                     if (carry) 64                         res.z[i] += base; 65                 } 66                 res.trim(); 67                 return res; 68             } 69             return -(v - *this); 70         } 71         return *this + (-v); 72     } 73  74     void operator*=(int v) { 75         if (v < 0) 76             sign = -sign, v = -v; 77         for (int i = 0, carry = 0; i < (int) z.size() || carry; ++i) { 78             if (i == (int) z.size()) 79                 z.push_back(0); 80             long long cur = z[i] * (long long) v + carry; 81             carry = (int) (cur / base); 82             z[i] = (int) (cur % base); 83             //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base)); 84         } 85         trim(); 86     } 87  88     Bigint operator*(int v) const { 89         Bigint res = *this; 90         res *= v; 91         return res; 92     } 93  94     friend pair
        
          divmod(const Bigint &a1, const Bigint &b1) { 95         int norm = base / (b1.z.back() + 1); 96         Bigint a = a1.abs() * norm; 97         Bigint b = b1.abs() * norm; 98         Bigint q, r; 99         q.z.resize(a.z.size());100 101         for (int i = a.z.size() - 1; i >= 0; i--) {102             r *= base;103             r += a.z[i];104             int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : 0;105             int s2 = b.z.size() - 1 < r.z.size() ? r.z[b.z.size() - 1] : 0;106             int d = ((long long) s1 * base + s2) / b.z.back();107             r -= b * d;108             while (r < 0)109                 r += b, --d;110             q.z[i] = d;111         }112 113         q.sign = a1.sign * b1.sign;114         r.sign = a1.sign;115         q.trim();116         r.trim();117         return make_pair(q, r / norm);118     }119 120     friend Bigint sqrt(const Bigint &a1) {121         Bigint a = a1;122         while (a.z.empty() || a.z.size() % 2 == 1)123             a.z.push_back(0);124 125         int n = a.z.size();126 127         int firstDigit = (int) sqrt((double) a.z[n - 1] * base + a.z[n - 2]);128         int norm = base / (firstDigit + 1);129         a *= norm;130         a *= norm;131         while (a.z.empty() || a.z.size() % 2 == 1)132             a.z.push_back(0);133 134         Bigint r = (long long) a.z[n - 1] * base + a.z[n - 2];135         firstDigit = (int) sqrt((double) a.z[n - 1] * base + a.z[n - 2]);136         int q = firstDigit;137         Bigint res;138 139         for(int j = n / 2 - 1; j >= 0; j--) {140             for(; ; --q) {141                 Bigint r1 = (r - (res * 2 * base + q) * q) * base * base + (j > 0 ? (long long) a.z[2 * j - 1] * base + a.z[2 * j - 2] : 0);142                 if (r1 >= 0) {143                     r = r1;144                     break;145                 }146             }147             res *= base;148             res += q;149 150             if (j > 0) {151                 int d1 = res.z.size() + 2 < r.z.size() ? r.z[res.z.size() + 2] : 0;152                 int d2 = res.z.size() + 1 < r.z.size() ? r.z[res.z.size() + 1] : 0;153                 int d3 = res.z.size() < r.z.size() ? r.z[res.z.size()] : 0;154                 q = ((long long) d1 * base * base + (long long) d2 * base + d3) / (firstDigit * 2);155             }156         }157 158         res.trim();159         return res / norm;160     }161 162     Bigint operator/(const Bigint &v) const {163         return divmod(*this, v).first;164     }165 166     Bigint operator%(const Bigint &v) const {167         return divmod(*this, v).second;168     }169 170     void operator/=(int v) {171         if (v < 0)172             sign = -sign, v = -v;173         for (int i = (int) z.size() - 1, rem = 0; i >= 0; --i) {174             long long cur = z[i] + rem * (long long) base;175             z[i] = (int) (cur / v);176             rem = (int) (cur % v);177         }178         trim();179     }180 181     Bigint operator/(int v) const {182         Bigint res = *this;183         res /= v;184         return res;185     }186 187     int operator%(int v) const {188         if (v < 0)189             v = -v;190         int m = 0;191         for (int i = z.size() - 1; i >= 0; --i)192             m = (z[i] + m * (long long) base) % v;193         return m * sign;194     }195 196     void operator+=(const Bigint &v) {197         *this = *this + v;198     }199     void operator-=(const Bigint &v) {200         *this = *this - v;201     }202     void operator*=(const Bigint &v) {203         *this = *this * v;204     }205     void operator/=(const Bigint &v) {206         *this = *this / v;207     }208 209     bool operator<(const Bigint &v) const {210         if (sign != v.sign)211             return sign < v.sign;212         if (z.size() != v.z.size())213             return z.size() * sign < v.z.size() * v.sign;214         for (int i = z.size() - 1; i >= 0; i--)215             if (z[i] != v.z[i])216                 return z[i] * sign < v.z[i] * sign;217         return false;218     }219 220     bool operator>(const Bigint &v) const {221         return v < *this;222     }223     bool operator<=(const Bigint &v) const {224         return !(v < *this);225     }226     bool operator>=(const Bigint &v) const {227         return !(*this < v);228     }229     bool operator==(const Bigint &v) const {230         return !(*this < v) && !(v < *this);231     }232     bool operator!=(const Bigint &v) const {233         return *this < v || v < *this;234     }235 236     void trim() {237         while (!z.empty() && z.back() == 0)238             z.pop_back();239         if (z.empty())240             sign = 1;241     }242 243     bool isZero() const {244         return z.empty() || (z.size() == 1 && !z[0]);245     }246 247     Bigint operator-() const {248         Bigint res = *this;249         res.sign = -sign;250         return res;251     }252 253     Bigint abs() const {254         Bigint res = *this;255         res.sign *= res.sign;256         return res;257     }258 259     long long longValue() const {260         long long res = 0;261         for (int i = z.size() - 1; i >= 0; i--)262             res = res * base + z[i];263         return res * sign;264     }265 266     friend Bigint gcd(const Bigint &a, const Bigint &b) {267         return b.isZero() ? a : gcd(b, a % b);268     }269     friend Bigint lcm(const Bigint &a, const Bigint &b) {270         return a / gcd(a, b) * b;271     }272 273     void read(const string &s) {274         sign = 1;275         z.clear();276         int pos = 0;277         while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {278             if (s[pos] == '-')279                 sign = -sign;280             ++pos;281         }282         for (int i = s.size() - 1; i >= pos; i -= base_digits) {283             int x = 0;284             for (int j = max(pos, i - base_digits + 1); j <= i; j++)285                 x = x * 10 + s[j] - '0';286             z.push_back(x);287         }288         trim();289     }290 291     friend istream& operator>>(istream &stream, Bigint &v) {292         string s;293         stream >> s;294         v.read(s);295         return stream;296     }297 298     friend ostream& operator<<(ostream &stream, const Bigint &v) {299         if (v.sign == -1)300             stream << '-';301         stream << (v.z.empty() ? 0 : v.z.back());302         for (int i = (int) v.z.size() - 2; i >= 0; --i)303             stream << setw(base_digits) << setfill('0') << v.z[i];304         return stream;305     }306 307     static vector
         
           convert_base(const vector
          
            &a, int old_digits, int new_digits) {308         vector
           
             p(max(old_digits, new_digits) + 1);309 p[0] = 1;310 for (int i = 1; i < (int) p.size(); i++)311 p[i] = p[i - 1] * 10;312 vector
            
              res;313 long long cur = 0;314 int cur_digits = 0;315 for (int i = 0; i < (int) a.size(); i++) {316 cur += a[i] * p[cur_digits];317 cur_digits += old_digits;318 while (cur_digits >= new_digits) {319 res.push_back(int(cur % p[new_digits]));320 cur /= p[new_digits];321 cur_digits -= new_digits;322 }323 }324 res.push_back((int) cur);325 while (!res.empty() && res.back() == 0)326 res.pop_back();327 return res;328 }329 330 typedef vector
             
               vll;331 332 static vll karatsubaMultiply(const vll &a, const vll &b) {333 int n = a.size();334 vll res(n + n);335 if (n <= 32) {336 for (int i = 0; i < n; i++)337 for (int j = 0; j < n; j++)338 res[i + j] += a[i] * b[j];339 return res;340 }341 342 int k = n >> 1;343 vll a1(a.begin(), a.begin() + k);344 vll a2(a.begin() + k, a.end());345 vll b1(b.begin(), b.begin() + k);346 vll b2(b.begin() + k, b.end());347 348 vll a1b1 = karatsubaMultiply(a1, b1);349 vll a2b2 = karatsubaMultiply(a2, b2);350 351 for (int i = 0; i < k; i++)352 a2[i] += a1[i];353 for (int i = 0; i < k; i++)354 b2[i] += b1[i];355 356 vll r = karatsubaMultiply(a2, b2);357 for (int i = 0; i < (int) a1b1.size(); i++)358 r[i] -= a1b1[i];359 for (int i = 0; i < (int) a2b2.size(); i++)360 r[i] -= a2b2[i];361 362 for (int i = 0; i < (int) r.size(); i++)363 res[i + k] += r[i];364 for (int i = 0; i < (int) a1b1.size(); i++)365 res[i] += a1b1[i];366 for (int i = 0; i < (int) a2b2.size(); i++)367 res[i + n] += a2b2[i];368 return res;369 }370 371 Bigint operator*(const Bigint &v) const {372 vector
              
                a6 = convert_base(this->z, base_digits, 6);373 vector
               
                 b6 = convert_base(v.z, base_digits, 6);374 vll a(a6.begin(), a6.end());375 vll b(b6.begin(), b6.end());376 while (a.size() < b.size())377 a.push_back(0);378 while (b.size() < a.size())379 b.push_back(0);380 while (a.size() & (a.size() - 1))381 a.push_back(0), b.push_back(0);382 vll c = karatsubaMultiply(a, b);383 Bigint res;384 res.sign = sign * v.sign;385 for (int i = 0, carry = 0; i < (int) c.size(); i++) {386 long long cur = c[i] + carry;387 res.z.push_back((int) (cur % 1000000));388 carry = (int) (cur / 1000000);389 }390 res.z = convert_base(res.z, 6, base_digits);391 res.trim();392 return res;393 }394 };395 396 int n;397 398 int main(){399 while(scanf("%d",&n)){400 if(n==0) break;401 Bigint ans=1;402 int a[30],cnt=0;403 for(int i=1;i<=n;i++){404 cin>>a[i];405 cnt+=a[i];406 }407 for(int i=1;i<=cnt;i++){408 ans*=i;409 }410 for(int i=1;i<=n;i++){411 for(int j=1;j<=a[i];j++){412 ans/=j;413 }414 }415 cout<
                
                 <

hdu 1261

hdu 1262

线性筛预处理一下素数，从m/2开始搜，第一个搜到的一定是最近的。

1 #include
      
        2 #define QAQ 0 3  4 using namespace std; 5 const int maxn=100000; 6 int prime[maxn],check[maxn]; 7 int m,n; 8  9 void xxs(){10     int tot=0;11     memset(check,0,sizeof(check));12     check[1]=1; 13     for(int i=2;i
       
        maxn) break;17             check[i*prime[j]]=1;18             if(i%prime[j]==0) break;19         }20     }21 } 22 23 int main(){24     xxs();25     while(scanf("%d",&m)!=EOF){26         n=m/2;27         while(1){28             if(!check[n] && !check[m-n]){29                 printf("%d %d\n",n,m-n);30                 break;31             }32             n--;33         }34     }35     return QAQ;36 }

hdu 1262

hdu 1263

二维map计数。

1 #include
      
        2 #define QAQ 0 3  4 using namespace std; 5  6 int N,M,a; 7 map
       
        
          >m; 8 string s1,s2; 9 10 int main(){11     cin>>N;12     while(N--){13         m.clear();14         cin>>M;15         for(int i=1;i<=M;i++){16             cin>>s1>>s2>>a;17             m[s2][s1]+=a;        18         }19         for(auto x:m){20             cout<
         
          <<'\n';21             for(auto y:x.second){22                 cout<<"   |----"<
          
           <<'('<
           
            <<')'<<'\n';23 }24 }25 if(N) cout<<'\n'; 26 }27 return QAQ;28 }

hdu 1263

hdu 1264

注意数据范围0到100...直接暴力扫。确定矩形位置的两个点有两种情况，一开始没swap掉坑里了。

1 #include
      
        2 #define QAQ 0 3  4 using namespace std; 5  6 int a1,b1,a2,b2; 7 bool m[102][102]; 8  9 int main(){10     while(1){11         memset(m,0,sizeof(m));12         int cnt=0;13         while(1){14             scanf("%d%d%d%d",&a1,&b1,&a2,&b2);15             if(a1==-1 || a1==-2) break;16             if(a1>a2) swap(a1,a2);17             if(b1>b2) swap(b1,b2);18             19             for(int i=b1;i

hdu 1264

hdu 1265

十六进制表示浮点数...挺奇特的...完全没想到这个思路。直接把计算机存放的二进制化成十六进制。。。

1 #include
      
        2 #define QAQ 0 3  4 using namespace std; 5  6 int N; 7 float f; 8  9 int main(){10     scanf("%d",&N);11     while(N--){12         scanf("%f",&f);13         unsigned char *p=(unsigned char *)&f;14         printf("%02X%02X%02X%02X\n",p[3],p[2],p[1],p[0]);15     }16     return QAQ;17 }

hdu 1265

hdu 1491

模拟题。

1 #include
      
        2 #define QAQ 0 3  4 using namespace std; 5  6 int T,a,b; 7 int m[13]={
    0,31,28,31,30,31,30,31,31,30,31,30,31}; 8  9 int main(){10     scanf("%d",&T);11     while(T--){12         scanf("%d%d",&a,&b);13         if(a>10 || (a==10&&b>21)){14             printf("What a pity, it has passed!\n");15         }16         else if(a==10 && b==21){17             printf("It's today!!\n");18         }19         else{20             if(a==10){21                 printf("%d\n",21-b);22             }23             else{24                 int ans=21+m[a]-b;25                 for(int i=a+1;i<=9;i++){26                     ans+=m[i];27                 }28                 printf("%d\n",ans);29             }30         }31     }32     return QAQ;33 }

hdu 1491

hdu 1492

因子只有2，3，5，7。统计它们的幂次，用求因数个数的公式就好。不开ll会wa。

1 #include
      
        2 #define QAQ 0 3  4 using namespace std; 5 typedef long long ll; 6  7 ll n; 8 ll f[4]={
    2,3,5,7},cnt[4]; 9 10 int main(){11     while(1){12         scanf("%lld",&n);13         if(n==0) break;14         ll ans=1;15         for(int i=0;i<4;i++){16             ll t=n;17             cnt[i]=0;18             while(t%f[i]==0){19                 cnt[i]++;20                 t/=f[i];21             }22             ans*=(cnt[i]+1);23         }24         printf("%lld\n",ans);25     }26     return QAQ;27 }

hdu 1492

hdu 1493

概率dp。本来想开二维，其实可以滚动，每次的概率以上次为基础。每次从后往前，dp[i]=dp[i]+dp[i-k]*rp[k]，k为掷出的点数。

1 #include
      
        2 #define QAQ 0 3 #define miaojie1 4 #ifdef miaojie 5   #define dbg(args...) do {cout << #args << " : "; err(args);} while (0) 6 void err() {std::cout << std::endl;} 7 template
       
         8 void err(T a, Args...args){std::cout << a << ' '; err(args...);} 9 #else10   #define dbg(...)11 #endif12 13 using namespace std;14 15 int T;16 double rp[10],dp[100];17 int a[11]={
    0,5,12,22,29,33,38,42,46,50,55};18 19 int main(){20     scanf("%d",&T);21     22     while(T--){23         for(int i=1;i<=6;i++){24             scanf("%lf",&rp[i]);25         }26         memset(dp,0,sizeof(dp));27         dp[0]=1;28         29         for(int i=1;i<=10;i++){30             dbg(dp[12]);31             for(int j=60;j>0;j--){32                 dp[j]=0;33                 for(int k=1;k<=6;k++){34                     if(j

hdu 1493

hdu 1494

还是dp。把n圈展开成线，能量看成0-14的整数，dp[i][j]表示到第i段时有j格能量所用的最短时间，顺序dp。注意j=0一定是刚用过加速卡，j=10可能是普通行驶或爆卡，j>10一定是普通行驶...分类挺麻烦的，状态方程分四个。感觉还可以简化下。

1 #include
      
        2 #define QAQ 0 3 #define miaojie1 4 #ifdef miaojie 5   #define dbg(args...) do {cout << #args << " : "; err(args);} while (0) 6 void err() {std::cout << std::endl;} 7 template
       
         8 void err(T a, Args...args){std::cout << a << ' '; err(args...);} 9 #else10   #define dbg(...)11 #endif12 13 using namespace std;14 typedef long long ll;15 16 int l,n;17 ll a[10020],b[10020],dp[10020][15];18 19 int main(){20     while(scanf("%d",&l)!=EOF){21         scanf("%d",&n);22         int sum=n*l;23         for(int i=1;i<=l;i++){24             scanf("%d",&a[i]);25             for(int j=1;j<=n-1;j++){26                 a[i+j*l]=a[i];27             }28         }29         for(int i=1;i<=l;i++){30             scanf("%d",&b[i]);31             for(int j=1;j<=n-1;j++){32                 b[i+j*l]=b[i];33             }34         }35         for(int i=0;i<=sum;i++){36             for(int j=0;j<15;j++){37                 dp[i][j]=1ll<<30;38             }39         }40         dp[0][0]=0;41         42         for(int i=1;i<=sum;i++){43             for(int j=0;j<15;j++){44                 if(j==0) {45                     dp[i][j]=dp[i-1][5]+b[i];    46                 }47                 else if(j==10){48                     dp[i][j]=min( dp[i-1][14]+a[i] , dp[i-1][9]+a[i] );49                 }50                 else if(j>10){51                     dp[i][j]=dp[i-1][j-1]+a[i];52                 }53                 else dp[i][j]=min( dp[i-1][j-1]+a[i] , dp[i-1][j+5]+b[i] );54             }55         }56         ll ans=1ll<<62;57         for(int i=0;i<15;i++){58             ans=min(ans,dp[sum][i]);59             dbg(dp[sum][i]);60         }61         printf("%lld\n",ans);62     }63     return QAQ;64 }

hdu 1494

hdu 1495

bfs，模拟每步的六种操作即可。

1 #include
      
         2 #define miaojie1  3 #ifdef miaojie  4   #define dbg(args...) do {cout << #args << " : "; err(args);} while (0)  5 void err() {std::cout << std::endl;}  6 template
       
          7 void err(T a, Args...args){std::cout << a << ' '; err(args...);}  8 #else  9   #define dbg(...) 10 #endif 11  12 using namespace std; 13  14 int S,s,n,m; 15 bool vis[105][105][105]; 16  17 struct node{ 18     int a,b,c,r; 19     node(){} 20     node(int _a,int _b,int _c,int _r) : a(_a),b(_b),c(_c),r(_r){} 21 }; 22  23 void bfs(){ 24     memset(vis,0,sizeof(vis)); 25     if(S%2){ 26         printf("NO\n"); 27         return; 28     } 29     else s=S/2; 30     queue
        
         q; 31     node st(S,0,0,0); 32     q.push(st); 33     vis[s][0][0]=1; 34      35     while(!q.empty()){ 36         node t=q.front(); 37         dbg(t.a,t.b,t.c,t.r); 38         if( (t.a==s&&t.b==s) || (t.a==s&&t.c==s) || (t.b==s&&t.c==s)){ 39             printf("%d\n",t.r); 40             return; 41         } 42         q.pop(); 43         if(t.a>0){ 44             node p=t; 45             if(p.a>=n-p.b){ 46                 p.a=p.a-(n-p.b); 47                 p.b=n; 48                 p.r++; 49             } 50             else{ 51                 p.b+=p.a; 52                 p.a=0; 53                 p.r++; 54             } 55             if(!vis[p.a][p.b][p.c]) q.push(p),vis[p.a][p.b][p.c]=1; 56              57             p=t; 58             if(p.a>=m-p.c){ 59                 p.a=p.a-(m-p.c); 60                 p.c=m; 61                 p.r++; 62             } 63             else{ 64                 p.c+=p.a; 65                 p.a=0; 66                 p.r++; 67             } 68             if(!vis[p.a][p.b][p.c]) q.push(p),vis[p.a][p.b][p.c]=1; 69              70             p=t; 71             if(p.b>=S-p.a){ 72                 p.b=p.b-(S-p.a); 73                 p.a=s; 74                 p.r++; 75             } 76             else{ 77                 p.a+=p.b; 78                 p.b=0; 79                 p.r++; 80             } 81             if(!vis[p.a][p.b][p.c]) q.push(p),vis[p.a][p.b][p.c]=1; 82              83             p=t; 84             if(p.b>=m-p.c){ 85                 p.b=p.b-(m-p.c); 86                 p.c=m; 87                 p.r++; 88             } 89             else{ 90                 p.c+=p.b; 91                 p.b=0; 92                 p.r++; 93             } 94             if(!vis[p.a][p.b][p.c]) q.push(p),vis[p.a][p.b][p.c]=1; 95              96             p=t; 97             if(p.c>=S-p.a){ 98                 p.c=p.c-(S-p.a); 99                 p.a=s;100                 p.r++;101             }102             else{103                 p.a+=p.c;104                 p.c=0;105                 p.r++;106             }107             if(!vis[p.a][p.b][p.c]) q.push(p),vis[p.a][p.b][p.c]=1;108             109             p=t;110             if(p.c>=n-p.b){111                 p.c=p.c-(n-p.b);112                 p.b=n;113                 p.r++;114             }115             else{116                 p.b+=p.c;117                 p.c=0;118                 p.r++;119             }120             if(!vis[p.a][p.b][p.c]) q.push(p),vis[p.a][p.b][p.c]=1;121         }122     }123     printf("NO\n");124 }125 126 int main(){127     while(1){128         scanf("%d%d%d",&S,&n,&m);129         if(S==0 && n==0 && m==0) break;130         bfs();131     }132     return 0;133 }

hdu 1495

hdu 1496

四个for显然超了，用折半法降时间复杂度，结果还是T，加了特判才过。由于有平方，只讨论正号省时间，最后乘16就行。

1 #include
      
        2  3 using namespace std; 4 typedef long long ll; 5  6 int a,b,c,d; 7 map
       
        mp; 8  9 int main(){10     while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF){11         if((a>0 && b>0 && c>0 && d>0) || (a<0 && b<0 && c<0 && d<0)){12             printf("0\n");13             continue;14         } 15         ll ans=0;16         mp.clear();17         for(int i=1;i<=100;i++){18             for(int j=1;j<=100;j++){19                 mp[a*i*i+b*j*j]++;20             }21         }22         for(int i=1;i<=100;i++){23             for(int j=1;j<=100;j++){24                 ans+=mp[-(c*i*i+d*j*j)];25             }26         }27         ans*=16;28         printf("%lld\n",ans);29     }30     return 0;31 }

hdu 1496

hdu 1497

怎么又是大模拟，8想做！不看它了！

hdu 1498

行对列匹配跑一遍二分图的最小覆盖,balabala（明天补上）

第二天：好像也补不上啥啊。。多一个匹配就多一个既不同行也不同列的气球，超过k个就不行了。

1 #include
      
        2 #define miaojie1 3 #ifdef miaojie 4   #define dbg(args...) do {cout << #args << " : "; err(args);} while (0) 5 void err() {std::cout << std::endl;} 6 template
       
         7 void err(T a, Args...args){std::cout << a << ' '; err(args...);} 8 #else 9   #define dbg(...)10 #endif11 using namespace std;12 13 int n,k,a[105][105],edge[105][105],cx[105],cy[105],ans[105],pp;14 bool vis[105];15 set
        
         se;16 17 int line(int u){18     for(int v=1;v<=n;v++){19         if(edge[u][v] && !vis[v]){20             vis[v]=1;21             if(cy[v]==-1 || line(cy[v])){22                 cx[u]=v;23                 cy[v]=u;24                 return 1;25             }26         }27     }28     return 0;29 }30 31 int mincover(){32     int ret=0;33     memset(cx,-1,sizeof(cx));34     memset(cy,-1,sizeof(cy));35     for(int i=1;i<=n;i++){36         if(cx[i]==-1){37             memset(vis,0,sizeof(vis));38             ret+=line(i);39         }40     }41     return ret;42 }43 44 int main(){45     while(1){46         scanf("%d%d",&n,&k);47         se.clear(); pp=0;48         if(n==0 && k==0) break;49         for(int i=1;i<=n;i++){50             for(int j=1;j<=n;j++){51                 scanf("%d",&a[i][j]);52                 se.insert(a[i][j]);53             }54         }55         for(auto x:se){56             dbg(x); 57             memset(edge,0,sizeof(edge));58             for(int i=1;i<=n;i++){59                 for(int j=1;j<=n;j++){60                     if(a[i][j]==x){61                         edge[i][j]=1;62                     }63                 }64             }65             if(mincover()>k) ans[pp++]=x;66         }67         dbg(pp);68         if(pp==0){69             printf("-1\n");70         }71         else{72             for(int i=0;i

hdu 1498

hdu 1728

一开始传统bfs，出队一个就搜四周，记录朝向来表示是否转弯，mle了。

其实这题应该换个想法，答案只和拐弯数有关，所以搜的时候可以不再前进一个点，改为一直走到某方向的尽头，路上的点还是判vis按顺序入队。这样每个点搜出一个十字形状，并且保证了第一次搜到时拐弯数最小。

定义了y1，没敢用万能头文件。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 9 int T,m,n;10 char a[105][105];11 bool vis[105][105];12 int k,x1,x2,y1,y2;13 int tx[5]={ 0,-1,0,1,0},ty[5]={ 0,0,1,0,-1};14 15 struct node{16 int x,y,r;17 node(){}18 node(int _x,int _y,int _r) : x(_x),y(_y),r(_r){}19 };20 21 void bfs(){22 queue
            
             q;23 vis[x1][y1]=1;24 // node st1(x1,y1,-1,1),st2(x1,y1,-1,2),st3(x1,y1,-1,3),st4(x1,y1,-1,4);25 // q.push(st1); q.push(st2); q.push(st3); q.push(st4);26 node st(x1,y1,-1);27 q.push(st);28 while(!q.empty()){29 node t=q.front();30 // cout<<"!!!"<
             
              <<" "<
              
               <<" "<
               
                <<" "<
                
                 k) continue;33 if(t.x==x2 && t.y==y2){34 // cout<<"~~~"<
                 
                  <<" "<
                  
                   <
                   
                    m||p.y<1||p.y>n||p.r>k||a[p.x][p.y]=='*')){ 44 if(!vis[p.x][p.y]){45 vis[p.x][p.y]=1;46 q.push(p);47 }48 p.x+=tx[i];49 p.y+=ty[i];50 }51 }52 }53 printf("no\n");54 }55 56 int main(){57 scanf("%d",&T);58 while(T--){59 scanf("%d%d",&m,&n);60 memset(vis,0,sizeof(vis));61 for(int i=1;i<=m;i++){62 for(int j=1;j<=n;j++){63 cin>>a[i][j];64 }65 }66 scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);67 bfs();68 } 69 return 0;70 }

hdu 1728

hdu 1729

sg函数太生疏了.....

s为容量，找到临界点t+t*t<s且(t+1)+(t+1)^2>=s，可知当盒子里大于t个时必胜，返回容量减现有个数（类比取石子），等于t时必败。小于t时无法判断，但s和t都是必败点，返回（t，c）等价。

1 #include
      
        2  3 using namespace std; 4  5 int n,cnt,s,c; 6  7 int SG(int s,int c){ 8     int t=sqrt(s); 9     while(t+t*t>=s){10         t--;11     }12     if(c>t) return s-c;13     else return SG(t,c);14 }15 16 int main(){17     while(1){18         scanf("%d",&n);19         if(n==0) break;20         int ans=0;21         for(int i=1;i<=n;i++){22             scanf("%d%d",&s,&c);23             ans^=SG(s,c);24         }25         printf("Case %d:\n",++cnt);26         if(ans) printf("Yes\n");27         else printf("No\n");28     }29     return 0;30 }

hdu 1729

hdu 1730

这题友好多了，每行两个棋子的距离-1其实就类比每堆石子数，nim一下就好。

1 #include
      
        2  3 using namespace std; 4  5 int n,m,a,b; 6  7 int main(){ 8     while(scanf("%d%d",&n,&m)!=EOF){ 9         int ans=0;10         for(int i=1;i<=n;i++){11             scanf("%d%d",&a,&b);12             ans=ans^(abs(a-b)-1);13         }14         if(!ans){15             printf("BAD LUCK!\n");16         }17         else printf("I WIN!\n");18     }19     return 0;20 }

hdu 1730

hdu 1732

bfs，记录人和三个箱子的位置。走一步——是否有障碍或箱子——若有箱子，箱子后面是否有障碍或其他箱子。

因为把=写成==爆内存了，找了一个小时，强行拉底ac率，很烦。

1 #include
      
        2  3 using namespace std; 4  5 struct node{ 6     int x[4],y[4],r; 7 }st; 8  9 int n,m;10 int tx[4]={-1,0,1,0},ty[4]={
    0,1,0,-1},endx[4],endy[4];11 char a[8][8];12 bool vis[8][8][8][8][8][8][8][8];13 queue
       
        q;14 void bfs(){15     memset(vis,0,sizeof(vis));16     while(!q.empty()) q.pop();17     q.push(st);18     while(!q.empty()){19         node t=q.front();20         q.pop();21         bool check=1;22         for(int i=1;i<=3;i++){23             bool ck=0;24             for(int j=1;j<=3;j++){25                 if(t.x[i]==endx[j] && t.y[i]==endy[j]) ck=1;26             }27             if(!ck){28                 check=0;29                 break;30             }31         }32         if(check){33             printf("%d\n",t.r);34             return;35         }36         if(vis[t.x[0]][t.y[0]][t.x[1]][t.y[1]][t.x[2]][t.y[2]][t.x[3]][t.y[3]]==1) continue;37         vis[t.x[0]][t.y[0]][t.x[1]][t.y[1]][t.x[2]][t.y[2]][t.x[3]][t.y[3]]==1;38         for(int i=0;i<=3;i++){39             node p=t;40             int f=0;41             p.x[0]+=tx[i];42             p.y[0]+=ty[i];43             p.r++;44             if(a[p.x[0]][p.y[0]]=='#'||p.x[0]>=n||p.x[0]<0||p.y[0]>=m||p.y[0]<0) continue;45             for(int j=1;j<=3;j++){46                 if(p.x[0]==p.x[j] && p.y[0]==p.y[j]){47                     f=j;48                     break;49                 }50             }51             if(f){52                 p.x[f]+=tx[i];53                 p.y[f]+=ty[i];54                 if(a[p.x[f]][p.y[f]]=='#'||p.x[f]>=n||p.x[f]<0||p.y[f]>=m||p.y[f]<0) continue;55                 bool ff=0;56                 for(int j=1;j<=3;j++){57                     if(j==f) continue;58                     if(p.x[f]==p.x[j] && p.y[f]==p.y[j]){59                         ff=1;60                         break;61                     }62                 }63                 if(!ff) q.push(p);64             }65             else{66                 q.push(p);67             }68         }69     }70     printf("-1\n");71 }72 73 int main(){74     ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);75     while(cin>>n>>m){76         int p=0,q=0;77         for(int i=0;i
        
         >a[i][j];80                 if(a[i][j]=='X'){81                     st.x[0]=i;82                     st.y[0]=j;83                 }84                 else if(a[i][j]=='*'){85                     st.x[++p]=i;86                     st.y[p]=j;87                 }88                 else if(a[i][j]=='@'){89                     endx[++q]=i;90                     endy[q]=j;91                 }92             }93         }94         st.r=0;95         bfs();96     }97     return 0;98 }

hdu 1732

hdu 6023

水题，模拟。

1 #include
      
        2  3 using namespace std; 4  5 int T,n,m,r,a,b,ans,cnt,pen[20]; 6 char c; 7 string s; 8 bool f[20]; 9 10 int main(){11     ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);12     cin>>T;13     while(T--){14         cin>>n>>m;15         memset(f,0,sizeof(f));16         memset(pen,0,sizeof(pen));17         ans=0;    cnt=0;18         while(m--){19             cin>>r>>a>>c>>b>>s;20             r-=1000;21             if(f[r]) continue;22             if(s[0]=='A'){23                 cnt++;24                 f[r]=1;25                 ans=ans+a*60+b+pen[r];26             }27             else{28                 pen[r]+=20;29             }30         }31         cout<
       
        <<" "<
        
         <<'\n';32     }33     return 0;34 }

hdu 6023

hdu 6024

dp[i][j]为前i个的最小花费，j=1表示第i个建，j=0表示不建。转移如下。其中dp[i][0]需要遍历一遍前面的情况。

1 #include
      
        2  3 using namespace std; 4 typedef long long ll; 5 struct node{ 6     ll x,c; 7     bool operator < (const node &t) const{ 8         return x
       
        =1;j--){28                 tmp=tmp+(i-j)*(a[j+1].x-a[j].x);29                 dp[i][0]=min(dp[i][0],dp[j][1]+tmp);30             }31         }32         printf("%lld\n",min(dp[n][0],dp[n][1]));33     }34     return 0;35 }

hdu 6024

hdu 6025

预处理前缀和后缀gcd，根据gcd的性质可以O(n)扫一遍得出答案。

1 #include
      
        2  3 using namespace std; 4 const int maxn=1e5+20; 5  6 int n,T,a[maxn],pre[maxn],las[maxn],ans; 7  8 int main(){ 9     scanf("%d",&T);10     while(T--){11         scanf("%d",&n);12         for(int i=1;i<=n;i++){13             scanf("%d",&a[i]);            14         }15         pre[1]=a[1]; las[n]=a[n];16         for(int i=2;i<=n;i++){17             pre[i]=__gcd(pre[i-1],a[i]);18         }19         for(int i=n-1;i>=1;i--){20             las[i]=__gcd(las[i+1],a[i]);21         }22         23         ans=max(pre[n-1],las[2]);24         for(int i=2;i<=n-1;i++){25             ans=max(ans,__gcd(pre[i-1],las[i+1]));26         }27         printf("%d\n",ans);28     }29     return 0;30 }

hdu 6025

hdu 6026

稍微修改一下djkstra板子，记录0到每个点的最短路有几条，由于最后一定各保留一条最短路，相乘即为选择的方案数。

1 #include
      
        2 #define inf 0x3f3f3f3f 3 #define miaojie1 4 #ifdef miaojie 5   #define dbg(args...) do {cout << #args << " : "; err(args);} while (0) 6 void err() {std::cout << std::endl;} 7 template
       
         8 void err(T a, Args...args){std::cout << a << ' '; err(args...);} 9 #else10   #define dbg(...)11 #endif12 using namespace std;13 typedef long long ll;14 typedef pair
        
         pii;15 const ll mod=1e9+7;16 const int maxn=3003;17 18 struct edge{19     int nxt,to,cost;20 }e[maxn];21 22 int n,head[55],d[55],cnt[55],p;23 ll ans;24 char s[55];25 bool vis[55];26 priority_queue
         
          
           ,greater
           
             >q;27 28 void addedge(int from,int to,int cost){29 e[p].nxt=head[from];30 e[p].to=to;31 e[p].cost=cost;32 head[from]=p++;33 }34 35 void DJ(){36 while(!q.empty()) q.pop();37 for(int i=0;i
            
             t.first+e[i].cost){52 d[e[i].to]=t.first+e[i].cost;53 cnt[e[i].to]=1;54 q.push(make_pair(d[e[i].to],e[i].to));55 }56 else if(d[e[i].to]==t.first+e[i].cost) cnt[e[i].to]++;57 }58 } 59 }60 61 int main(){62 while(~scanf("%d",&n)){63 memset(head,-1,sizeof(head)); p=0; ans=1;64 for(int i=0;i

hdu 6026

hdu 6027

水题，预处理一下暴力能过。

1 #include
      
        2  3 using namespace std; 4 typedef long long ll; 5 const ll mod=1e9+7; 6  7 int T; 8 ll n,k,f[10002][7]; 9 10 void init(){11     for(int i=1;i<=10000;i++){12         f[i][0]=1;13         for(int j=1;j<=5;j++){14             f[i][j]=f[i][j-1]*i%mod;15         }16     }17 }18 19 int main(){20     scanf("%d",&T);21     init();22     while(T--){23         scanf("%lld%lld",&n,&k);24         ll ans=0;25         for(int i=1;i<=n;i++){26             ans=(ans+f[i][k])%mod;27         }28         printf("%lld\n",ans);29     }30     return 0;31 }

hdu 6027

hdu 6029

寻找是否存在完美匹配，从后往前贪心即可，尽量让后面的连接。

1 #include
      
        2  3 using namespace std; 4  5 int T,n,a[100005];  6  7 int main(){ 8     scanf("%d",&T); 9     while(T--){10         scanf("%d",&n);11         int cnt=0;12         for(int i=2;i<=n;i++){13             scanf("%d",&a[i]);14             if(a[i]==1) cnt++;15         }16         if(n%2||cnt
       
        =2;i--){24             if(a[i]==2) f--;25             else f++;26             if(f<0){27                 jd=0;28                 break;29             }30         }31         if(jd) printf("Yes\n");32         else printf("No\n");33     } 34     return 0;35 }

hdu 6029

hdu 6030

红记为1，蓝记为0，题目条件转化为连续2个或3个珠子中1的个数>=0的个数。考虑在2个连续的珠子后增加一个，有10-->101->01 , 01->011->11 , 11->111或110->11或10；

记末尾10的个数为f(a)，末尾01的个数为f(b)，末尾11的个数为f(c)，总个数f(n)；

则f(a+1)=f(c)，f(b+1)=f(a)，f(c+1)=f(b)+f(c)；

根据以上关系推出f(n)=f(n-1)+f(n-3)，显然可以用矩阵快速幂解决。

1 #include
      
        2  3 using namespace std; 4 typedef long long ll; 5 const int mod=1e9+7; 6 const int z = 3; 7  8 int T; 9 ll n;10 struct ju{11     long long a[z][z];12 };13 14 ju muli(ju A,ju B){15     ju C;16     for(int i=0;i

hdu 6030

hdu 6032

在贾老板的指导下勉强混过了。

三个map分别存子串是否出现、出现次数、对应的sg。结构体存胜负，顺便存分数，dfs跑sg的时候记得每次交换自己(p1)和对手(p2)。做着难受，I very vegetable.

1 #include
      
        2 #define inf 0x3f3f3f3f 3 #define miaojie1 4 #ifdef miaojie 5   #define dbg(args...) do {cout << #args << " : "; err(args);} while (0) 6 void err() {std::cout << std::endl;} 7 template
       
         8 void err(T a, Args...args){std::cout << a << ' '; err(args...);} 9 #else10   #define dbg(...)11 #endif12 using namespace std;13 14 struct node{15     int flag;16     int p1,p2;17     node(){}18     node(bool _flag,int _p1,int _p2) : flag(_flag),p1(_p1),p2(_p2){}19     bool operator < (const node &a)const{20         if(flag==a.flag){21             if(p2==a.p2){22                 return p1
        
         a.p2;25         }26         return flag
         
          jd;31 map
          
           
             >cnt;32 map
            
             sg;33 int n;34 char s[100];35 36 node dfs(string s){37 if(sg.count(s)){38 return sg[s];39 }40 node t{ 1,inf,0};41 string ts;42 for(char i='a';i<='z';i++){43 if(jd.count(s+i)) t=min(t,dfs(s+i));44 if(jd.count(i+s)) t=min(t,dfs(i+s));45 }46 47 int sum=0,maxi=0;48 for(int i=0;i