首页 > 其他 > 详细

8.19总结今日

时间:2018-08-19 10:45:47      阅读:151      评论:0      收藏:0      [点我收藏+]

今天打到一半网站崩了,所以没能继续打,话说开火车好烦hhh


 

开火车D题

题意:

有一个n*m的矩阵,上面一共有k*k个蛋糕,让你横向纵向都切k-1刀,问能不能存在一种切法使得切完的所有区域都正好只剩一个蛋糕,如果有,输出切的位置

解法:

由于横竖切互不影响,所以我们分开考虑这两部分,先算出每一行(列)有的蛋糕总数,然后每k个切一次,看看能不能

 1 #include<cstdio>
 2 using namespace std;
 3 const int maxn = 200 + 5;
 4 int g[maxn][maxn];
 5 int row[maxn], col[maxn];
 6 int ansr[maxn], ansc[maxn];
 7 
 8 int main() {
 9     int n, m, k; scanf("%d%d%d", &n, &m, &k);
10     for (int i = 0; i < n; i++) 
11         for (int j = 0; j < m; j++) 
12             scanf("%1d", &g[i][j]);
13 
14     //处理每一列
15     for (int j = 0; j < m; j++) 
16         for (int i = 0; i < n; i++) 
17             row[j] += g[i][j];
18     
19     int now = 0, cnt = 0, flag = 1;
20     for (int j = 0; j < m; j++) {
21         now += row[j];
22         if (now < k)continue;
23         else if (now == k) { now = 0, ansr[cnt++] = j; }
24         else if (now > k) { flag = false; break; }
25     }
26     if (!flag) { printf("NO\n"); return 0; }
27 
28     //处理每一行
29     for (int i = 0; i < n; i++) 
30         for (int j = 0; j < m; j++) 
31             col[i] += g[i][j];
32 
33     now = 0, cnt = 0, flag = 1;
34     for (int i = 0; i < n; i++) {
35         now += col[i];
36         if (now < k)continue;
37         else if (now == k) { now = 0, ansc[cnt++] = i; }
38         else if (now > k) { flag = false; break; }
39     }
40     if (!flag) { printf("NO\n"); return 0; }
41 
42     //如果可以的话
43     printf("YES\n");
44     printf("%d", ansc[0]+1);
45     for (int i = 1; i < k-1; i++)printf(" %d", ansc[i]+1);
46     printf("\n%d", ansr[0]+1);
47     for (int i = 1; i < k-1; i++)printf(" %d", ansr[i]+1);
48     printf("\n");
49 
50     return 0;
51 }

洛谷P1062

题意:

给出一个多项式的各个项的系数,输出这个多项式

解法:

超tm细心的模拟,竟然调了这么长时间,简直了

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int main() {
 5     int n; cin >> n;
 6     int cnt = n, flag = 0, flag2 = 0;
 7     for (int i = 0; i <= n; i++,cnt--) {
 8         int coe; cin >> coe;
 9         if (coe==0)continue;
10         if (i != n)flag2 = 1;
11         if (flag && coe > 0 && i != 0 && flag2)cout << "+";
12         if (i == 0) {
13             if (coe == -1)cout << "-";
14             else if (coe != 1)cout << coe;
15             cout << "x^" << cnt;
16             flag = 1;
17             continue;
18         }
19         else if (i == n) cout << coe, flag = 1;
20         else if (i == n - 1) {
21             if (coe == -1)cout << "-";
22             else if (coe != 1)cout << coe;
23             cout << "x";
24             flag = 1;
25         }
26         else {
27             if (coe == -1)cout << "-";
28             else if (coe != 1)cout << coe;
29             cout << "x^" << cnt;
30             flag = 1;
31         }
32     }
33     if (!flag)cout << 0;
34     cout << endl;
35     return 0;
36 }

Uva1635

题意:

给定n个数a1,a2····an,依次求出相邻两个数值和,将得到一个新数列,重复上述操作,最后结果将变为一个数,问这个数除以m的余数与那些数无关?

例如n=3,m=2时,第一次得到a1+a2,a2+a3,再求和得到a1+2*a2+a3,它除以2的余数和a2无关。1=<n<=10^5, 2=<m<=10^9

解法:

将所有的加法过程列出来可以得到,n个数合并成1个数需要n-1步,且最后的表达式写成初始项相加的形式 每一项的系数恰好就是一个二项式系数。

问除以m的余数与那些数无关,其实就是问这些因子中哪些是m的倍数。我们还是用分解m质因子的方法,将m的质因子全部先分解出来,然后遍历每个二项式系数,看他们能否整除这些质因子(如果这个二项式系数改写成质因子的幂次形式,的这个幂小于m中的这个幂,就不行) 。

除此之外还要学习的就是怎么计算这个幂次,尤其是被除数为分数的时候,分子的幂次的贡献为正,分母为负

 1 #include<cstdio>
 2 #include<vector>
 3 #include<cstring>
 4 using namespace std;
 5 int vis[100000 + 5];
 6 
 7 int work_quality_factor(int n, int quality_fac[], int frequency[])
 8 {//n是待分解的数,quality_fac[]会存放它包含的质因子,而frequency[]存放对应次数
 9  //如q_f[k]=7,fre[k]=2就表示质因数分解后里面包含有7,且次数是2
10  //函数返回有几种质因子,比如分解了25就返回1,分解28返回2
11     int res, temp, i;
12     res = 0;
13     temp = n;
14     for (i = 2; i*i <= temp; i++)
15         if (temp%i == 0)
16         {
17             quality_fac[res] = i;
18             frequency[res] = 0;
19             while (temp%i == 0)
20             {
21                 temp = temp / i;
22                 frequency[res]++;
23             }
24             res++;
25         }
26     if (temp > 1)
27     {
28         quality_fac[res] = temp;
29         frequency[res++] = 1;
30     }
31     return res;
32 }
33 
34 int main() {
35     int n, m;
36     while (scanf("%d%d", &n, &m) != EOF) {
37         n--;
38         memset(vis, 0, sizeof(vis));
39         int fac[100], frq[100];
40         int primenum = work_quality_factor(m, fac, frq);
41 
42         for (int i = 0; i < primenum; i++) {
43             int min_e = frq[i], x, e = 0;
44             // c(n,k)=c(n,k-1)*(n-k+1)/k
45             for (int k = 1; k < n; k++) {
46                 //分成上下两部分除,上面的幂次的贡献为正,下面为负
47                 x = n - k + 1;
48                 while (x%fac[i]==0) { x /= fac[i]; e++; }
49                 x = k;
50                 while (x%fac[i]==0) { x /= fac[i]; e--; }
51                 if (e < min_e)vis[k] = 1;
52             }
53         }
54         
55         vector<int>ans;
56         for (int i = 1; i < n; i++)
57             if (!vis[i])ans.push_back(i + 1);
58         printf("%d\n", ans.size());
59         if (!ans.empty()) {
60             printf("%d", ans[0]);
61             for (int i = 1; i < ans.size(); i++)
62                 printf(" %d", ans[i]);
63         }
64         printf("\n");
65     }
66     return 0;
67 }

Uva10820

题意:

给出n,算出小于等于n的所有数中,有几对互质;

解法:

本质就是求有多少个2元组(x,y)满足:1 <= x,y <= n,且x与y互素。

除了(1,1)之外,其他所有的x和y都不相同,我们设x<y的二元组有f(n)个,答案就是2f(n)+1 f(n)=phi(2)+phi(3)+...+phi(n);

 1 #include<cstdio>
 2 #include<cmath>
 3 using namespace std;
 4 const int maxn = 5e4 + 5;
 5 int phi[maxn];
 6 
 7 //欧拉函数,求小于n且与n互素的整数个数
 8 int euler_phi(int n) {
 9     int m = (int)sqrt(n + 0.5);
10     int ans = n;
11     for (int i = 2; i <= m; i++) if (n%i == 0) {
12         ans = ans / i*(i - 1);
13         while (n%i == 0)n /= i;
14     }
15     if (n > 1)ans = ans / n*(n - 1);
16     return ans;
17 }
18 
19 //求小于n的所有数的欧拉函数值
20 void phi_table(int n, int *phi) {
21     for (int i = 2; i <= n; i++)phi[i] = 0;
22     phi[1] = 1;
23     for (int i = 2; i <= n; i++)if (!phi[i])
24         for (int j = i; j <= n; j += i) {
25             if (!phi[j])phi[j] = j;
26             phi[j] = phi[j] / i*(i - 1);
27         }
28 }
29 
30 int main() {
31     int n;
32     while (scanf("%d", &n) && n) {
33         phi_table(n, phi);
34         int ans = 0;
35         for (int i = 2; i <= n; i++) ans += phi[i];
36         printf("%d\n", ans + ans + 1);
37     }
38     return 0;
39 }

Uva1636

题意:

扣一下枪没有响,问再扣一下抢还没有响的概率,这是把左轮枪

解法:

求出00的概率和01串的概率即可,注意这个是环形的左轮枪

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 char s[1000];
 5 
 6 int main() {
 7     while (scanf("%s", s) != EOF) {
 8         int len = strlen(s);
 9         int pr = 0, pc = 0, gun = 0;
10         s[len] = s[0], s[len + 1] = \0;
11         len = strlen(s);
12         for (int i = 0; i < len - 1; i++) 
13             if (s[i] == 0&&s[i + 1] == 0)pr++;
14         for (int i = 0; i < len-1; i++)
15             if (s[i] == 0)gun++;
16         if (pr*(len-1) > gun*gun)printf("SHOOT\n");
17         else if (pr*(len-1) == gun*gun)printf("EQUAL\n");
18         else printf("ROTATE\n");
19     }
20     return 0;
21 }

Uva580

题意:

一个栈中只能放入U和L,问存在连续3个以上U(危险组合)的个数为几个

解法:

危险情况数 = 总组合数 - 安全情况数

f[i]表示第i个位置是L的方法总数,那么f[i]=f[i-1]+f[i-2]+f[i-3]

 1 #include<cstdio>
 2 using namespace std;
 3 typedef long long ll;
 4 ll f[31];
 5 
 6 void generate() {
 7     f[1] = 2, f[2] = 4, f[3] = 7;
 8     for (int i = 4; i <= 30; i++) {
 9         f[i] = f[i - 1] + f[i - 2] + f[i - 3];
10     }
11 }
12 
13 int main() {
14     int n; 
15     generate();
16     while (scanf("%d", &n) && n) {
17         ll ans = (1 << n);
18         printf("%lld\n", ans - f[n]);
19     }
20     return 0;
21 }

 

8.19总结今日

原文:https://www.cnblogs.com/romaLzhih/p/9499458.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!