第二次练习

题目描述
你有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

#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;
}

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

#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;
            else
                maxn = mid - 1;
        }
        printf("%dn", minn);
    }
    return 0;
}

//用优先队列，一直对当前最大值进行操作
#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 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();
	}
}

#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';
	}
} 

#include
#include
#include
using namespace std;
int a[6][12];
int b[6];
typedef pair PII;
vector 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().swap(s); 
    }
}

#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;
	}
}

#include
#include
#include
using namespace std;
int col[110],row[110];
vector 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().swap(s);
	}
 } 

#include
#include
#include 
#include
using namespace std;
priority_queue,greater> 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;
} 

这道题巨恶心，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] = '';
                }
            } 
            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] = '';
                }
                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] = '';
                }
            }
            if(str[0] == '') cout << "Over" << endl;
            else{
                for(int u = 0;str[u] != '';u ++)
                cout << str[u];
                cout << 'n';
            }
        }
        cout << 'n';
    }
    return 0;
}

#include
#include
using namespace std;
list 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::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;
 }