第二次练习

骰子

题目

题目描述
你有n颗六面骰子，每个面上有一个数字，你随机地抛掷这n颗骰子，求各骰子顶面数字和的出现概率。

比如你有2颗骰子，那么它们的六面的数都是1∼6，那么出现的数字和是2∼12,其出现的概率依次为（省略）

输入格式

第一行是一个整数T (1≤T≤50),表示测试样例的个数。

以后每个样例的第一行是一个整数n(1≤n≤8)，表示骰子的个数。 以后的n行，每行6个整数ai (1≤ai≤1024)，表示第i个骰子六面上的数字。

输出格式

依次输出每个样例。

先输出会出现多少种数字；然后每行按出现数字和，从小到大输出，一个数字输出1行，格式如”n: x/y”，其中n为出现的数字，x/y为出现的概率分数，保证x,y互质。英文冒号后有一个空格。

样例输入

2
1
1 1 2 2 3 3
2
1 2 3 4 5 6
1 2 3 4 5 6

样例输出

3
1: 1/3
2: 1/3
3: 1/3
11
2: 1/36
3: 1/18
4: 1/12
5: 1/9
6: 5/36
7: 1/6
8: 5/36
9: 1/9
10: 1/12
11: 1/18
12: 1/36

谢大题解

AC代码

#include
#include
using namespace std;
int a[8][6];
int b[8];
int c[10010];
long long gcd(long long x,long long  y){return !y?x:gcd(y,x%y);}
int main()
{int T;cin >> T;while(T --){int n; cin >> n;//输入各个骰子点数 for(int i = 0;i < n;i ++)for(int j = 0;j < 6;j ++) cin >> a[i][j];//初始化所有可能点数和值为0 for(int i = 0;i < 10010;i ++)c[i] = 0;int u,cnt; //炮灰变量 long long q = pow(6,n);//要遍历每个骰子的点数，遍历次数是pow(6,n) for(int i = 0;i < q;i ++){//遍历次数转化成六进制，位数为每个骰子的点数//这里初始化b数组，这个数组用来存放每个骰子的点数 for(int j = 0;j < 8;j ++)b[j] = 0;cnt = 0; u = i;//十进制转化六进制 while(u){int t = u % 6;b[cnt] = t;//存放在数组中 cnt ++;u/=6;} int sum = 0;//每个骰子的点数和 for(int j = 0;j < n;j ++){sum += a[j][b[j]];}c[sum] ++;}cnt = 0;//统计有多少种值 for(int i = 0;i < 10010;i ++){if(c[i]) cnt ++;}cout << cnt << endl;//遍历c数组，有值的话得出答案 for(int i = 0;i < 10010;i ++){if(c[i]){cout << i << ":" << ' ' << c[i]/gcd(c[i],q) << "/" << q/gcd(c[i],q) << endl;}}}return 0;
}

记录一下我当时觉得可能要花很长时间做出来的题。

1244

#include
#include
using namespace std;
//题目的思路是 ：答案的值在整个数列的最小值和总和之间取。
//限制条件是：分组的数目要小于m
int a[10010];int main(){ios::sync_with_stdio(false);int T;cin >> T;int n,m;while (T --){cin >> n >> m;int maxn = 0,minn = 0;for(int i = 0;i < n;i ++){cin >> a[i];maxn += a[i];//求最大值 minn = max(minn,a[i]);//求最小值 }int res, sum, mid;while (minn <= maxn){sum = 0;int mid = (minn + maxn) >> 1;//取值二分 //找数目res = 1;for(int i = 0;i < n;i ++){sum += a[i];if(sum > mid) {++ res;sum = 0;i --;}} if (res > m)minn = mid + 1;elsemaxn = mid - 1;}printf("%d\n", minn);}return 0;
}

1262

//用优先队列，一直对当前最大值进行操作
#include
#include
#include
using namespace std;
typedef struct node {int a, b;bool operator < (const node & n) const {return a < n.a;}
} Node;
priority_queue<node> st;//当前维护的n个鱼塘能钓到的鱼
int main()
{int T; cin >> T;while(T --){Node s;int sum = 0; int n,m; cin >> n >> m;for(int i = 0;i < n;i ++) {cin >> s.a >> s.b;st.push(s);}//每次钓鱼找能钓鱼最多的鱼塘 for(int j = 0;j < m;j ++){Node t = st.top();//取最大值 st.pop();sum += t.a;//更新t.a = max(0,t.a - t.b);st.push(t);if(st.empty()) break;}cout << sum << '\n';while (!st.empty()) st.pop();}
}

1269

#include
#include
using namespace std;
const int N = 1010;
typedef long long LL;
LL a[N],b[N];
int main()
{int T;cin >> T;LL ans;int k,n;while(T --){LL low = 0,high = 2e9;cin >> n >> k;for(int i = 0;i < n;i ++) cin >> a[i];for(int i = 0;i < n;i ++) cin >> b[i];//用k二分找出能做出的成品数目 while(low <= high){LL mid = (low + high) >> 1;//求需要多少材料LL sum = 0;LL t;for(int i = 0;i < n;i ++){t = mid * a[i] - b[i];if(t > 0) sum += t;}if(k >= sum) low = mid + 1;else high = mid - 1;} cout << high << '\n';}
} 

1275

#include
#include
#include
using namespace std;
int a[6][12];
int b[6];
typedef pair<int,int> PII;
vector<PII> s;//记录答案 
//初始化 
void init()
{for(int i = 1;i <= 5;i ++){for(int j = 1;j <= 11;j ++){a[i][j] = 0;}b[i] = 0;}
}
void print(int i)
{if(i == 1) cout << "Mon" << " ";else if(i == 2) cout << "Tue" << " ";else if(i == 3) cout << "Wen" << " ";else if(i == 4) cout << "Thur" << " ";else cout << "Fri" << " ";
}
int main()
{ios::sync_with_stdio(false);int T; cin >> T;while(T --){int N,T;//上课时间段和考试时间。cin >> N >> T;init();//上课时间while(N --){char tim[5]; int st,ed;cin >> tim >> st >> ed;if(!strcmp(tim,"Mon")) for(int j = st;j <= ed;j ++) a[1][j] = 1;//标记else if(!strcmp(tim,"Tue")) for(int j = st;j <= ed;j ++) a[2][j] = 1;//标记else if(!strcmp(tim,"Wen")) for(int j = st;j <= ed;j ++) a[3][j] = 1;//标记else if(!strcmp(tim,"Thur")) for(int j = st;j <= ed;j ++) a[4][j] = 1;//标记else if(!strcmp(tim,"Fri")) for(int j = st;j <= ed;j ++) a[5][j] = 1;//标记}//开始找时间考试int sum;int t;int ans = 0;for(int i = 1;i <= 5;i ++){//上午 for(int j = 1;j <= 4;j ++){sum = 0;if(!a[i][j]){t = j;while(!a[i][t] && t <= 4) {sum ++;t ++;}if(sum >= T){for(int u = j;u <= j + sum - T;u ++)s.push_back({u,u + T - 1});ans += sum - T + 1;}j = t - 1;}}//下午for(int j = 5;j <= 8;j ++){sum = 0;if(!a[i][j]){t = j;while(!a[i][t] && t <= 8) {sum ++;t ++;}if(sum >= T){for(int u = j;u <= j + sum - T;u ++)s.push_back({u,u + T - 1});ans += sum - T + 1;}j = t - 1;}}//晚上for(int j = 9;j <= 11;j ++){sum = 0;if(!a[i][j]){t = j;while(!a[i][t] && t <= 11) {sum ++;t ++;}if(sum >= T){for(int u = j;u <= j + sum - T;u ++)s.push_back({u,u + T - 1});ans += sum - T + 1;}j = t - 1;}} b[i] = ans;} //输出答案cout << ans << '\n';for(int j = 0;j < ans;j ++){if(j < b[1]){print(1);cout << s[j].first << ' ' << s[j].second << '\n';} else if(j < b[2]){print(2);cout << s[j].first << ' ' << s[j].second << '\n';}else if(j < b[3]){print(3);cout << s[j].first << ' ' << s[j].second << '\n';}else if(j < b[4]){print(4);cout << s[j].first << ' ' << s[j].second << '\n';}else{print(5);cout << s[j].first << ' ' << s[j].second << '\n';}}	//清空容器vector<PII>().swap(s); }
}

1423

#include
#include
using namespace std;
int a[1010];
int main()
{ios::sync_with_stdio(false);int T; cin >> T;while(T --){int n; cin >> n;int sum = 0; for(int i = 0;i < n;i ++) cin >> a[i];sort(a,a + n);for(int i = 0;i < n - 2;i ++)for(int j = i + 1;j < n - 1;j ++){int x = a[i] + a[j];int l = j + 1,r = n - 1;while(l < r){int mid = l + r + 1 >> 1;if(x > a[mid]) l = mid;else r = mid - 1;}if(l < n && a[r] < x) {sum += l - j;//		cout << r << ' ' << i << ' ' << j << endl;}}cout << sum << endl;}
}

1408

#include
#include
#include
using namespace std;
int col[110],row[110];
vector<int> s;
int main()
{ios::sync_with_stdio(false);int T; cin >> T;while(T --){int n,m,p,k;cin >> n >> m >> p >> k;for(int i = 1;i <= n || i <= m ;i ++){row[i] = 0;col[i] = 0;}for(int i = 0;i < p;i ++){int x1,y1,x2,y2;cin >> x1 >> y1 >> x2 >> y2;if(x1 != x2 && y1 == y2) row[min(x1,x2)] ++;if(y1 != y2 && x1 == x2) col[min(y1,y2)] ++;}for(int i = 1;i <= m;i ++){if(row[i]) s.push_back(row[i]);}for(int i = 1;i <= n;i ++){if(col[i])s.push_back(col[i]);		}int len = s.size();int sum = 0; //	for(int i = 0;i < len;i ++) cout << s[i] << endl; if(len <= k) cout << 0 << ' ' << len << endl;else{sort(s.begin(),s.end());for(int i = 0;i < len - k;i ++)sum += s[i];cout << sum << endl;}vector<int>().swap(s);}} 

1417

#include
#include
#include 
#include
using namespace std;
priority_queue<int,vector<int>,greater<int>> q;
char s[2010];
int a[26];
int main()
{ios::sync_with_stdio(false);while(~scanf("%s",s)){for(int i = 0;i < 26;i ++) a[i] = 0;int len = strlen(s);for(int i = 0;i < len;i ++) {a[s[i] - 'a'] ++;}for(int i = 0;i < 26;i ++){if(a[i])q.push(a[i]);}int ans = 0;while(q.size() > 1){int a = q.top(); q.pop();int b = q.top(); q.pop();ans += (a + b) * (a + b);q.push(a + b);}cout << ans << endl;q.pop();}return 0;
} 

1419

这道题巨恶心，pe的问题一直报wa…

#include
using namespace std;
char str[35];
int main()
{ios::sync_with_stdio(false);int n,T;cin >> T;while(T --){cin >> str >> n;while(n --){int x;cin >> x; x --;int i,j,c,d;c = x; d = x + 1;swap(str[c],str[d]);if(str[x] == str[x + 1]){for(i = x;i >= 0;i --){if(str[i] == str[x])c = i;else break;}for(i = x + 1;str[i];i ++){if(str[i] == str[x])d = i;else break;}if(d - c + 1 >= 3){for(i = c,j = d + 1;str[j];i ++,j ++) str[i] = str[j];str[i] = '\0';}} else{for(i = x + 1;str[i];i ++){if(str[i] == str[x + 1])d = i;else break;}if(d - (x + 1) + 1 >= 3){for(i = x + 1,j = d + 1;str[j];i ++,j ++) str[i] = str[j];str[i] = '\0';}for(i = x;i >= 0;i --){if(str[i] == str[x])c = i;else break;}if(x - c + 1 >= 3){for(i = c,j = x + 1;str[j];i ++,j ++) str[i] = str[j];str[i] = '\0';}}if(str[0] == '\0') cout << "Over" << endl;else{for(int u = 0;str[u] != '\0';u ++)cout << str[u];cout << '\n';}}cout << '\n';}return 0;
}

1432

#include
#include
using namespace std;
list<int> l;
int a[1010];
int main()
{ios::sync_with_stdio(false);int T; cin >> T;while(T --){int n;cin >> n >> a[1] >> a[2];for(int i = 3;i < n;i ++) a[i] = (a[i - 1] + a[i - 2])%n + 1;for(int i = 1;i <= n;i ++) l.push_back(i);int cnt = 1;list<int>::iterator st = l.begin();while(l.size() > 1){int i = a[cnt] - 1;while(i --){st ++;if(st == l.end()) st = l.begin();}st = l.erase(st);if(st == l.end()) st = l.begin();cnt ++;}cout << *st << endl;l.clear();}return 0;} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！