BC #33

2015-03-15 11:46:09 总结： 　　.... 最近状态实在是太差了，一直在刷水题 Orz .... 　　比赛中智商下线... A题 wa数次才
2023-10-24 技术

2015-03-15 11:46:09

总结：

　　.... 最近状态实在是太差了，一直在刷水题 Orz ....

　　比赛中智商下线... A题 wa数次才过，B题高精度过pretest，后来TLE了.... 最近要多做做比赛恢复一下状态了。

 

A：手速题.... 打太快导致粗心的错误... （全局变量清空和>=的问题）

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include <set>
 8 #include 
 9 #include 
10 #include <string>
11 #include 
12 #include 
13 using namespace std;
14 
15 #define MEM(a,b) memset(a,b,sizeof(a))
16 #define REP(i,n) for(int i=1;i<=(n);++i)
17 #define REV(i,n) for(int i=(n);i>=1;--i)
18 #define FOR(i,a,b) for(int i=(a);i<=(b);++i)
19 #define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
20 #define getmid(l,r) ((l) + ((r) - (l)) / 2)
21 #define MP(a,b) make_pair(a,b)
22 
23 typedef long long ll;
24 typedef pair<int,int> pii;
25 const int INF = (1 << 30) - 1;
26 
27 int tlen,n,B;
28 char ts[300];
29 int s[300],ans[300];
30 
31 inline int Trans(char cur){
32     if(cur >= '0' && cur <= '9') return cur - '0';
33     return cur - 'a' + 10;
34 }
35 
36 int main(){
37     while(scanf("%d%d",&n,&B) != EOF){
38         int max_len = 0;
39         MEM(ans,0);
40         REP(i,n){
41             scanf("%s",ts);
42             tlen = strlen(ts);
43             max_len = max(max_len,tlen);
44             for(int j = 0; j < tlen; ++j) s[tlen - 1 - j] = Trans(ts[j]);
45             if(i == 1) for(int j = 0; j < tlen; ++j) ans[j] = s[j];
46             else for(int j = 0; j < tlen; ++j) ans[j] = (ans[j] + s[j]) % B;
47         }
48         int i;
49         for(i = max_len - 1; i >= 0; --i) if(ans[i] != 0) break;
50         if(i < 0) printf("0");
51         for(; i >= 0; --i){
52             if(ans[i] >= 10) printf("%c",'a' + ans[i] - 10);
53             else printf("%d",ans[i]);
54         }
55         puts("");
56     }
57     return 0;
58 }
View Code

 

B：本来是个水快速幂，答案就是2^n - 2，特判一下n=1的情况。然而，坑爹的是，因为数据范围而需要高精度 / 快速乘法。（当然也可以用java）

     下面来普及一下快速乘法，（下图摘自noip吧）：

　　　　

　　由于类似快速幂，所以以上被称为快速乘法。计算x * y % p时，如果 x，y，x*y%p 均不超过范围，但是x * y会超过范围。

　　这时候，快速乘法就派上用场了，把y化成其二进制形式，就变成：y = 2^k1 + 2^k2 + ... + 2^km，而x * y = x * (2^k1 + 2^k2 + ... + 2^km)

　　看到这里，由于分配律，乘法也可以二进制拆分。

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include <set>
 8 #include 
 9 #include 
10 #include <string>
11 #include 
12 #include 
13 using namespace std;
14 
15 #define MEM(a,b) memset(a,b,sizeof(a))
16 #define REP(i,n) for(int i=1;i<=(n);++i)
17 #define REV(i,n) for(int i=(n);i>=1;--i)
18 #define FOR(i,a,b) for(int i=(a);i<=(b);++i)
19 #define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
20 #define getmid(l,r) ((l) + ((r) - (l)) / 2)
21 #define MP(a,b) make_pair(a,b)
22 
23 typedef long long ll;
24 typedef pair<int,int> pii;
25 const int INF = (1 << 30) - 1;
26 
27 ll n,p;
28 
29 ll Mul(ll x,ll y){
30     ll res = 0;
31     while(y){
32         if(y & 1){
33             res += x;
34             while(res > p) res -= p;
35         }
36         x += x;
37         while(x > p) x -= p;
38         y >>= 1;
39     }
40     return res;
41 }
42 
43 ll Q_pow(ll x,ll y){
44     ll res = 1;
45     while(y){
46         if(y & 1) res = Mul(res,x);
47         x = Mul(x,x);
48         y >>= 1;
49     }
50     return res;
51 }
52 
53 int main(){
54     ios::sync_with_stdio(false);
55     while(cin >> n >> p){
56         if(n == 1){
57             if(p == 1) printf("0\n");
58             else printf("1\n");
59             continue;
60         }
61         cout << (Q_pow(2LL,n) - 2 + p) % p << endl;
62     }
63     return 0;
64 }
View Code

 

java版本：

 1 import java.util.Scanner;
 2 import java.math.BigInteger;
 3 
 4 public class Main {
 5     public static void main(String[] args){
 6         Scanner in = new Scanner(System.in);
 7         BigInteger n,p,ans;
 8         BigInteger two = new BigInteger("2");
 9         while(in.hasNext()){
10             n = in.nextBigInteger();
11             p = in.nextBigInteger();
12             ans = Q_pow(two,n,p).add(p).subtract(two).mod(p);
13             System.out.println(ans);
14         }
15         in.close();
16     }
17     static BigInteger Q_pow(BigInteger x,BigInteger y,BigInteger p){
18         BigInteger two = new BigInteger("2");
19         BigInteger res = new BigInteger("1");
20         BigInteger zero = BigInteger.ZERO;
21         while(y.compareTo(zero) > 0){
22             if(y.mod(two).compareTo(zero) != 0){
23                 res = res.multiply(x).mod(p);
24             }
25             x = x.multiply(x).mod(p);
26             y = y.divide(two);
27         }
28         return res;
29     }
30 }
View Code

 

C：背包是比较明显的... 题解给了状压DP。

　  然后看了别人的做法，大部分是O（30*10000）的 “暴力” DP。dp[i]表示前i个单位的时间能获得的最大分数。

　  逐个考虑每个题目，dp[i] = max（dp[i]，dp[i - t[i]] + v[i]）。

　  当然直接从1到n扫会有问题，我们应该把问题按照 l - t （即最早可能的起点）排序，这样可以使得晚开始的问题可以继承早开始的问题更新的dp值。

　  这样写很容易T，要剪枝，（1）处理出当前最大的可能时间，（2）实时更新答案，比如当前ans=10，那么时间>10的情况就不用考虑了。

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include <set>
 8 #include 
 9 #include 
10 #include <string>
11 #include 
12 #include 
13 using namespace std;
14 
15 #define MEM(a,b) memset(a,b,sizeof(a))
16 #define REP(i,n) for(int i=1;i<=(n);++i)
17 #define REV(i,n) for(int i=(n);i>=1;--i)
18 #define FOR(i,a,b) for(int i=(a);i<=(b);++i)
19 #define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
20 #define getmid(l,r) ((l) + ((r) - (l)) / 2)
21 #define MP(a,b) make_pair(a,b)
22 
23 typedef long long ll;
24 typedef pair<int,int> pii;
25 const int INF = (1 << 30) - 1;
26 const int MAXN = 40;
27 
28 int n,w;
29 struct node{
30     int t,v,l;
31     bool operator < (const node &b) const{
32         return l - t < b.l - b.t;
33     }
34 }nd[MAXN];
35 
36 ll dp[3000010];
37 
38 int main(){
39     while(scanf("%d%d",&n,&w) != EOF){
40         ll sumv = 0;
41         REP(i,n){
42             scanf("%d%d%d",&nd[i].t,&nd[i].v,&nd[i].l);
43             sumv += nd[i].v;
44         }
45         if(sumv < w){
46             printf("zhx is naive!\n");
47             continue;
48         }
49         if(w == 0){
50             puts("0");
51             continue;
52         }
53         MEM(dp,0);
54         sort(nd + 1,nd + n + 1);
55         int ans = INF,sum = 0;
56         REP(i,n){
57             int bot = max(nd[i].l,nd[i].t);
58             sum += bot; //剪枝（1）
59             sum = min(sum,ans); //剪枝（2）
60             for(int j = 2; j <= sum; ++j) dp[j] = max(dp[j],dp[j - 1]);
61             for(int j = sum; j >= bot; --j){
62                 dp[j] = max(dp[j],dp[j - nd[i].t] + nd[i].v);
63                 if(dp[j] >= w) ans = min(ans,j);
64             }
65         }
66         printf("%d\n",ans);
67     }
68     return 0;
69 }
View Code

 

转载于:https://www.cnblogs.com/naturepengchen/articles/4340061.html

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！

推荐阅读