1.饿饿，饭饭2

题目链接：饿饿饭饭2 - Problem - Daimayuan Online Judge

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main() {
 5     int T;
 6     cin >> T;
 7     while (T--) {
 8         int n;
 9         cin >> n;
10         int a[n];
11         for (int i = 0; i < n; i++) {
12             cin >> a[i];
13         }
14         bool flag = true;
15         for (int i = 0; i < n; i++) {
16             while (a[i] % 2 == 0) {
17                 a[i] /= 2;
18             }
19             while (a[i] % 3 == 0) {
20                 a[i] /= 3;
21             }
22             if (a[i] != a[0]) {
23                 flag = false;
24                 break;
25             }
26         }
27         if (flag) {
28             cout << "YES" << endl;
29         } else {
30             cout << "NO" << endl;
31         }
32     }
33     return 0;
34 }

2.子串分值和

题目链接：子串分值和 - Problem - Daimayuan Online Judge

暴力会TLE，加上每一个元素的贡献值和O(N)的复杂度，算一下每一个字母对自己及后面的贡献值

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e6+10;
 4 string s;
 5 int cnt[26];
 6 signed main()
 7 {
 8     cin>>s;
 9     long long res=0;
10     for(int i=0;i<s.length();i++)
11     {
12         
13         for(int j=i;j<s.length();j++)
14         {
15             memset(cnt,0,sizeof cnt);
16             for(int k=i;k<=j;k++)
17             {
18                 if(cnt[s[k]-'a'])continue;
19                 cnt[s[k]-'a']++;
20             }
21             for(int i=0;i<26;i++)
22                 res+=cnt[i];
23         }
24     }
25     
26     cout<<res;
27 }

3.蒟蒻

题目链接：蒟蒻 - Problem - Daimayuan Online Judge

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 map<int,int>m1;//第一关键字：m1是价格，m2是口感 
 5 map<int,int>m2;
 6 signed main()
 7 {
 8     scanf("%d",&n);
 9     while(n--)
10     {
11         int op,w,t;
12         scanf("%d",&op);
13         if(op==1) 
14         {
15             scanf("%d%d",&w,&t);
16             if(m1.count(w)==0 && m2.count(t)==0)
17             {
18                 m1[w]=t;
19                 m2[t]=w;
20             }    
21         }
22         else if(op==2)
23         {//必须先清除掉m2，要不先m1会数据丢失 
24             m2.erase(m1.begin()->second);
25             m1.erase(m1.begin());
26         }
27         else if(op==3)
28         {//必须先清除m1,要不先m2的话m1清除的就错了 
29             m1.erase(m2.begin()->second);
30             m2.erase(m2.begin());
31 
32         }
33     }    
34     int res=0;
35     for(auto x:m1)
36     {
37         res+=x.first;
38     }
39     printf("%d",res);
40 }

4.锦标赛

题目链接：锦标赛 - Problem - Daimayuan Online Judge

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e5+10;
 4 int a[N];
 5 long long res=1;
 6 int n,k;
 7 signed main()
 8 {
 9      scanf("%d%d",&n,&k);
10      for(int i=0;i<n;i++) scanf("%d",&a[i]);
11      sort(a,a+n,greater<int>());
12      for(int i=0;i<n-1;i++)
13      {
14          if(a[i]-a[i+1] <=k)res++;
15          else break;
16      }
17      printf("%d",res);
18 }

5.可重排列

题目链接：可重排列 - Problem - Daimayuan Online Judge

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 LL sum,res;
 5 int n;
 6 const int N=10;
 7 int a[N];
 8 vector<int>v;
 9 void dfs()
10 {
11     if(v.size()==sum)
12     {
13         for(auto i:v)printf("%d ",i);
14 //        for(int i=0;i<v.size();i++) printf("%d ",v[i]);
15         printf("\n");
16         return;
17     }
18     for(int i=1;i<=n;i++)
19     {
20         if(a[i]!=0)
21         {
22             a[i]--;
23             v.push_back(i);
24             dfs();
25             v.pop_back();
26             a[i]++;
27         }
28     }
29 }
30 signed main()
31 {
32     scanf("%d",&n);
33     for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i];//此时a[i]存储的是1~n的数字总数 
34     dfs();
35     return 0;
36 }

6.掷骰子：

假设你有m个n面骰子（点数∈[1，n],求掷这m个骰子，点数和大于等于k的概率，结果保留两位小数（可使用f'{num :.2%}'格式化输出，使num以百分数形式并保留2为小数输出). 提示：可以模拟该过程，先编写函数求出点数和等于某个值的概率，再进行累加.1≤m,n≤6 输入输出格式：输入格式：一行由空格隔开的三个数字，分别代表m,n,k 输出格式：一行数字，表示概率。

题目样例：
输入：
1 6 6
输出：
16.67%
输入：
2 6 11
输出：
8.33%

注意：%%转移是百分号＋百分号，而大多数都是\转义

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int m, n, k;
 5 double dp[7][42]; // 注意数组大小
 6 
 7 int main() {
 8     cin >> m >> n >> k;
 9 
10     // 初始化 dp 数组
11     for (int j = 1; j <= n; j++) {
12         dp[1][j] = 1.0 / n;
13     }
14 
15     // 计算 dp 数组
16     for (int i = 2; i <= m; i++) {
17         for (int j = i; j <= m * n; j++) {
18             for (int p = 1; p <= n; p++) {
19                 if (j - p > 0) {
20                     dp[i][j] += dp[i - 1][j - p]/n;
21                 }
22             }
23         }
24     }
25 
26     // 计算最终概率
27     double p = 0;
28     for (int j = k; j <= m * n; j++) {
29         p += dp[m][j];
30     }
31 
32     // 输出结果
33     printf("%.2f%%\n", p * 100);
34 
35     return 0;
36 }

 1 def dice_probability(n: int, sum: int) -> float:
 2     """
 3     求掷 n 个 6 面骰子，点数和等于 sum 的概率
 4     """
 5     if sum < n or sum > n * 6:
 6         return 0  # 和小于 n 或大于 6n，概率为 0
 7     dp = [0] * (sum + 1)
 8     dp[0] = 1
 9     for i in range(1, n + 1):
10         for j in range(sum, i - 1, -1):
11             dp[j] = 0
12             for k in range(1, 7):
13                 if j - k >= i - 1:
14                     dp[j] += dp[j - k] / 6
15     return dp[sum]
16 
17 m, n, k = map(int, input().split())
18 p = sum(dice_probability(m, i) for i in range(k, m * n + 1))
19 print(f'{p :.2%}')

526互联

ACM预备队-大一下学期week(3)集训

1.饿饿，饭饭2