NEUQ2020-ACM实验班-训练003

╰+哭是因爲堅強的太久メ 2021-09-07 06:01 1020阅读 0赞

# 最短路径之Dijkstra +口罩发放 +破译报文+小何的旅行I +运动会+Many Possibilities… +字母排列问题 +子串 +刮刮彩票 +求所有N位的素数和 #

> **AC码出自卷群全体成员**  
> 有时间一定回来打注释

### 文章目录 ###

*  最短路径之Dijkstra +口罩发放 +破译报文+小何的旅行I +运动会+Many Possibilities... +字母排列问题 +子串 +刮刮彩票 +求所有N位的素数和
 *   *  7-1 最短路径之Dijkstra (10分)
     *  7-2 口罩发放 (10分)
     *  7-3 破译报文 (10分)
     *  7-4 小何的旅行I (10分)
     *  7-5 运动会 (10分)
     *  7-6 So Many Possibilities... (10分)
     *  7-7 字母排列问题 (10分)
     *  7-8 子串 (10分)
     *  7-9 刮刮彩票 (10分)
     *  7-10 求所有N位的素数和 (10分)

## 7-1 最短路径之Dijkstra (10分) ##

> 本题目要求通过读入无向网的边的信息（省略了各顶点的信息，仅用顶点编号来表示），构造图，并利用Dijkstra算法，求出指定源点到其它各点的最短路径。  
> **输入样例:**
> 
> 第一行，两个整数，顶点数vN和边数eN。  
> 以后若干行，是相关边的信息，无向图的边是对称的，只输入一半的边（小编号到大编号的，间以空格），最后两行各一个整数，前一个指定源点，后一个指定的查询的终到点。  
> （注意，示例中34条边，只输入了17条边的信息）
> 
> 10 34 0 1 2 0 3 5 1 2 5 1 3 2 2 4 8 2 5 4 3 5 4 3 6 2 4 7 5 4 5 2 5 6  
> 3 5 7 9 5 8 7 6 8 7 7 8 3 7 9 4 8 9 8 0 8
> 
> **输出样例**:
> 
> 在一行中输出从源点到指定终点的短路径及代价，注意：所有符号均为西文符号。
> 
> 0–>1–>3–>6–>8:13

#include<stdio.h>
    #define max 1000
    #define n 100
    void DIJ(float C[n][n],int v,int q)
    { 
        float D[n];
        int P[n],S[n];
        int i,j,k,v1,pre;
        float min,inf=200;
        v1=v-1;
        for(i=0;i<n;i++)
        { 
            D[i]=C[v1][i];
            if(D[i]!=max)
                P[i]=v;
            else P[i]=0;
        }
        for(i=0;i<n;i++)
            S[i]=0;
        S[v1]=1;
        D[v1]=0;
        for(i=0;i<n-1;i++)
        { 
            min=inf;
            for(j=0;j<n;j++)
                if((!S[j])&&(D[j]<min))
                { 
                    min=D[j];
                    k=j;
                }
                S[k]=1;
                for(j=0;j<n;j++)
                    if((!S[j])&&(D[j]>D[k]+C[k][j]))
                    { 
                        D[j]=D[k]+C[k][j];
                        P[j]=k+1;
                    }
        }
            i=q-1;
            pre=P[i];
            j=0;
            int b[n];
            while(pre!=0)
            { 
                b[j]=pre;
                j++;
                pre=P[pre-1];
            }
            printf("%d-->",v-1);
            for(k=j-2;k>=0;k--)
            { 
                printf("%d-->",b[k]-1);
            }
            if(D[i]!=max)
            printf("%d:%.0f",i,D[i]);
    }
    main()
    { 
        int i,j,k,e,r;
        float z;
        float a[n][n];
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                a[i][j]=max;
        scanf("%d%d",&r,&e);
        for(k=0;k<e/2;k++)
        { 
            scanf("%d%d%f",&i,&j,&z);
            a[i][j]=z;
            a[j][i]=z;
        }
        scanf("%d",&i);
        scanf("%d",&j);
        DIJ(a,i+1,j+1);
    }

## 7-2 口罩发放 (10分) ##

> 为了抗击来势汹汹的 COVID19 新型冠状病毒，全国各地均启动了各项措施控制疫情发展，其中一个重要的环节是口罩的发放。
> 
> 某市出于给市民发放口罩的需要，推出了一款小程序让市民填写信息，方便工作的开展。小程序收集了各种信息，包括市民的姓名、身份证、身体情况、提交时间等，但因为数据量太大，需要根据一定规则进行筛选和处理，请你编写程序，按照给定规则输出口罩的寄送名单。  
> **输入格式:**
> 
> 输入第一行是两个正整数 D 和 P（1≤D,P≤30），表示有 D 天的数据，市民两次获得口罩的时间至少需要间隔 P 天。
> 
> 接下来 D 块数据，每块给出一天的申请信息。第 i 块数据（i=1,⋯,D）的第一行是两个整数 Ti 和  
> Si（1≤Ti,Si≤1000），表示在第 i 天有 Ti 条申请，总共有 Si 个口罩发放名额。随后  
> Ti 行，每行给出一条申请信息，  
> **格式如下：**
> 
> 姓名 身份证号 身体情况 提交时间
> 
> **给定数据约束如下**：
> 
>     姓名 是一个长度不超过 10 的不包含空格的非空字符串；
>     身份证号 是一个长度不超过 20 的非空字符串；
>     身体情况 是 0 或者 1，0 表示自觉良好，1 表示有相关症状；
>     提交时间 是 hh:mm，为24小时时间（由 00:00 到 23:59。例如 09:08。）。注意，给定的记录的提交时间不一定有序；
>     身份证号 各不相同，同一个身份证号被认为是同一个人，数据保证同一个身份证号姓名是相同的。
> 
> 能发放口罩的记录要求如下：
> 
>     身份证号 必须是 18 位的数字（可以包含前导0）；
>     同一个身份证号若在第 i 天申请成功，则接下来的 P 天不能再次申请。也就是说，若第 i 天申请成功，则等到第 i+P+1 天才能再次申请；
>     在上面两条都符合的情况下，按照提交时间的先后顺序发放，直至全部记录处理完毕或 Si 个名额用完。如果提交时间相同，则按照在列表中出现的先后顺序决定。
> 
> **输出格式**:
> 
> 对于每一天的申请记录，每行输出一位得到口罩的人的姓名及身份证号，用一个空格隔开。顺序按照发放顺序确定。
> 
> 在输出完发放记录后，你还需要输出有合法记录的、身体状况为 1  
> 的申请人的姓名及身份证号，用空格隔开。顺序按照申请记录中出现的顺序确定，同一个人只需要输出一次。  
> **输入样例:**
> 
> 4 2 5 3 A 123456789012345670 1 13:58 B 123456789012345671 0 13:58 C  
> 12345678901234567 0 13:22 D 123456789012345672 0 03:24 C  
> 123456789012345673 0 13:59 4 3 A 123456789012345670 1 13:58 E  
> 123456789012345674 0 13:59 C 123456789012345673 0 13:59 F F 0 14:00 1  
> 3 E 123456789012345674 1 13:58 1 1 A 123456789012345670 0 14:11
> 
> **输出样例:**
> 
> D 123456789012345672 A 123456789012345670 B 123456789012345671 E  
> 123456789012345674 C 123456789012345673 A 123456789012345670 A  
> 123456789012345670 E 123456789012345674
> 
> **样例解释：**
> 
> 输出中，第一行到第三行是第一天的部分；第四、五行是第二天的部分；第三天没有符合要求的市民；第六行是第四天的部分。最后两行按照出现顺序输出了可能存在身体不适的人员。

#include<bits/stdc++.h>
    using namespace std;
    map<string,int>mp,mp2;
    struct node
    { 
    	string name;
    	string id;
    	int num,hh,mm,t,idx;
    	char time[15];	
    }a[50005],b[50005];
    int cmp(node a,node b)
    { 	
    	if(a.t!=b.t)
    	return a.t<b.t;   
    	else
    	return a.idx<b.idx;
    }
    int check(string n)
    { 	
    	if(n.length()!=18)
    	return 0;
    	for(int i=0;i<n.length();i++)
    	{ 
    		if(!isdigit(n[i]))
    		return 0;
    	}
    	return 1;
    }
    int main()
    { 
    	int D,P,g=0;
    	cin>>D>>P;
    	for(int i=1;i<=D;i++)
    	{ 
    		int T,S;
    		cin>>T>>S;	
    		for(int j=0;j<T;j++)
    		{ 	
    			cin>>a[j].name>>a[j].id>>a[j].num>>a[j].time;
    			a[j].idx=j; 
    			if(mp.find(a[i].id)==mp.end())
    			mp[a[i].id]=0;
    			if(a[j].num==1&&mp2.find(a[j].id)==mp2.end()&&check(a[j].id))
    			{ 
    				mp2[a[j].id]=0;
    				b[g++]=a[j];
    			}	
    			sscanf(a[j].time,"%d:%d",&a[j].hh,&a[j].mm); 
    			a[j].t=a[j].hh*60+a[j].mm;
    		}
    		sort(a,a+T,cmp);
    		int cnt=0;
    		for(int j=0;j<T&&cnt<S;j++) 
    		{ 
    			if(check(a[j].id)&&((mp[a[j].id]+P+1<=i)||mp[a[j].id]==0))
    			{ 
    				cout<<a[j].name<<" "<<a[j].id<<endl;
    				cnt++;
    				mp[a[j].id]=i;
    			}	
    		}
    	}
    	for(int i=0;i<g;i++)
    	cout<<b[i].name<<" "<<b[i].id<<endl;
    	return 0;
    }

## 7-3 破译报文 (10分) ##

> 小明接到一个破解报文的任务：该报文是一串文本，破解出的密文应是在报文串中出现次数大于1的所有子串中的最长者。规定报文本身不能称为自己的子串。请编写效率尽可能高的程序帮小明完成这个棘手的任务。  
> **输入格式:**
> 
> 输入为一个字符串，表示报文，包含不超过10000个字母。 输出格式:
> 
> 输出为一个整数，表示破解出的密文串的长度。 输入样例1:
> 
> xabceabcf
> 
> **输出样例1:**
> 
> 3
> 
> **输入样例2:**
> 
> xyabcabcayx
> 
> **输出样例2:**
> 
> 4

#include<bits/stdc++.h>
    using namespace std;
    
    struct word
    { 
    	long long num;
    	long long addr[10000];
    }b[200];
    
    int  main()
    { 
    	long long length=0;
    	long long ans=0;
    	char a[10005];
    	long long k=1;
    	a[k]=getchar();
    	while(a[k]!='\n')
    	{ 
    		k++;
    		a[k]=getchar();
    	}
    	for(long long i=1;i<k;i++)
    	{ 
    		
    		
    		if(b[(long long)a[i]].num==0)
    		{ 
    			
    			b[(long long)a[i]].num++;
    			b[(long long)a[i]].addr[1]=i;
    		}
    		else
    		{ 
    			b[(long long)a[i]].num++;
    			b[(long long)a[i]].addr[b[(long long)a[i]].num]==i;
    			for(long long j=1;j<b[(long long)a[i]].num;j++)
    			{ 
    				for(ans=0;;ans++)
    				{ 
    					if(a[b[(long long)a[i]].addr[j]+ans]==a[i+ans]) continue;
    					else
    					{ 
    						length = max( length , ans);
    						break;
    					}
    				} 
    			}
    			i=i+length-1;
    		}
    	}
    	cout<<length;
    }

## 7-4 小何的旅行I (10分) ##

> 有一天小何来到一个陌生的星球上旅游，但这边的钱币上印有奇奇怪怪的符号和字母，小何看不懂，但他又想买东西（不吃东西要饿死的！），而你是在那个星球上唯一认识的人，于是就找来你帮他翻译下。
> 
> 这个星球上不同的种族分别收不一样币种的钱币，而小何想买的东西也来自不同种族所开的店铺，因此他想知道，他手里的钱币换成另一种钱币它的币值将会变成多少。
> 
> 那边的钱币不同的面额采用不同的进制，而且也没有阿拉伯数字，只有小写字母和符号表示，字母表示数字，而符号则表示它的币种（也就是代表是几进制的）。  
> 符号 代表  
> \#7进制 $17进制 ^ 2进制
> 
> 而字母和数字的对应表如下： 字母 代表 a 0 b 1 c 2 … … j 9 k 10 l 11 … …
> 
> 例如种类为\#的一个合法的币值为：\#abc, \#bfa。 输入描述
> 
> 第一行仅包含一个整数T(1≤T≤100)，代表有T组样例。
> 
> 接下来的T行，每行包含一个币值和一个要求转换的目标币种。(数据保证没有前导0，也就是不存在类似\#abc这种由a开头的币值，同时也不会有0元这种存在。保证币值的长度不超过70，目标币种仅为1个字符。)
> 
> **提示:**  
> 数据范围较大，请使用long long类型代替int。  
> **输出描述**
> 
> 输出目标币种的币值（不能出现前导0）。  
> **输入样例**
> 
> 3  
> \#bac ^  
> $bahdgm \#  
> ^bab \#
> 
> **输出样例**
> 
> ^bbaabb  
> \#bfceaedg  
> \#f
> 
> 提示
> 
> 现将输入的币值换成十进制，再转换哦！

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    void shizhuank(ll n,int k);
    int main()
    { 
        int n;
        cin>>n;
        while(n--)
        {  
        int k;
        char a[70];
        cin>>a;
        int len=strlen(a);
        char x;
        cin>>x;
        if(a[0]=='#')k=7;
        else if(a[0]=='$')k=17;
        else k=2;
        ll sum=0,kk=1;
        for(int j=len-1;j>0;j--)
        { 
            int aa=a[j]-97;
            sum+=kk*aa;
            kk*=k;
        }
        int xk;
        if(x=='#')xk=7;
        else if(x=='$')xk=17;
        else xk=2;
        cout<<x;
        shizhuank(sum,xk);
        }
    }
    void shizhuank(ll n,int k)
    {  
        ll a,m=0,s[100];
    	while(n!=0)
    	{ 
    		a=n%k;
    		n=n/k;
    		m++;
    		s[m]=a;  
    	}
        for(int i=m;i>=1;i--)
        { 
            char a;
            a=s[i]+97;
            cout<<a;
        }
        cout<<endl;
    }

## 7-5 运动会 (10分) ##

> T公司的员工层级关系可以表示成一棵树，员工X是员工Y的直接领导，则在树中X是Y的父结点。公司拟组织一场运动会，但为了避免尴尬，每个员工都不想与自己的直接领导一起参赛。假定每个员工都对应一个权重（领导的权重不一定比下属大），请你编写程序，邀请若干员工参赛，使得参赛人员的总权重和最大。  
> **输入格式:**
> 
> 第一行一个正整数n，表示公司的员工人数，员工编号为1…n，n不超过3000。  
> 接下来n行，每行1个整数，表示每个员工的权重，值域为\[−27,27)。  
> 接下来n-1行，每行为两个空格间隔的整数X和Y，表示Y是X的直接领导。 输出格式:
> 
> 输出为一个整数，表示参赛员工的最大权重之和。  
> **输入样例:**
> 
> 7 2 2 2 2 2 2 2 2 1 3 1 4 2 5 2 6 3 7 3
> 
> **输出样例:**
> 
> 10

#include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    ll a[3005];
    int main()
    { 
    	ll n;
    	cin >> n;
    	
    	for (ll i = 1; i <= n; i ++) scanf("%d", &a[i]);
    	
    	ll x, y;
    	for (ll i = 1; i <= n - 1; i ++)
    	{ 
    		scanf("%lld%lld", &x, &y);
    		a[y] -= a[x];
    	}
    	
    	ll sum = 0;
    	for (ll i = 1; i <= n; i ++)
    	{ 
    		if (a[i] < 0) continue;
    		else sum += a[i];
    	}
    	cout << sum;
    	
    	return 0;
    }

## 7-6 So Many Possibilities… (10分) ##

> Hearthstone is a free-to-play online digital collectible card game  
> developed and published by Blizzard Entertainment. The game is a  
> turn-based card game between two opponents, using constructed decks of  
> 30 cards along with a selected hero with a unique power. Players use  
> their limited mana crystals to cast spells or summon minions to attack  
> the opponent, with the goal of destroying the opponent’s hero.
> 
> Kurisu loves playing Hearthstone and plays her Highlander Mage deck  
> very well. However, sometimes she isn’t lucky enough, so that when she  
> plays the card Reno the Relicologist (as shown in the image below), it  
> always fails to kill many of the enemy minions. Now she wonders, given  
> the n enemy minions on board and their remaining health, if she may  
> deal m damage randomly split among them, what is the expected number  
> of enemy minions that would be killed?  
> ![Reno-the-Relicologist-300x414.png][]
> 
> Figure 1: Reno the Relicologist
> 
> One may think of dealing m damage randomly split among minions as m  
> separate one-damage hits, processed one by one. Each one-damage hit  
> targets a minion with positive health uniformly at random, and then  
> decreases its health by one. Note that the one-damage hit will never  
> be distributed to a dying minion, i.e., a minion whose health is  
> already zero.
> 
> Since there are so many possibilities in this process, please help her  
> calculate the expected number of minions with zero health after the  
> process above.  
> **Input Specification:**
> 
> The first line of input contains two integers n (1≤n≤15) and m  
> (1≤m≤100), the number of minions and the total amount of damage to  
> distribute.
> 
> The second line contains n integers a\_1,a\_2,\\dots,a\_n  
> (1≤ai≤100,∑ai≥m), where ai denotes the remaining health of  
> the i-th minion.  
> **Output Specification:**
> 
> Output the expected number of minions killed during the process within  
> an absolute error of no more than 10−6.  
> **Sample Input 1:**
> 
> 2 2 2 2
> 
> **Sample Output 1:**
> 
> 0.5
> 
> **Sample Input 2:**
> 
> 3 3 1 2 3
> 
> **Sample Output 2:**
> 
> 1.0833333333333333

#include<bits/stdc++.h>
    using namespace std;
    
    typedef long long LL;
    typedef long double LD;
    typedef pair<LL,LL> pii;
    typedef pair<double, double> pdd;
    const int SZ = 50100;
    const double INF = 1e10 + 10;
    const int mod = 998244353;
    const LD eps = 1e-8;
    
    LL read() { 
        LL n = 0;
        char a = getchar();
        bool flag = 0;
        while(a > '9' || a < '0') {  if(a == '-') flag = 1; a = getchar(); }
        while(a <= '9' && a >= '0') {  n = n * 10 + a - '0',a = getchar(); }
    	if(flag) n = -n;
    	return n;
    }
    
    
    int n,m,a[117];
    double f[117][SZ],C[110][110];
    double g[117][110];
    double G[110][SZ];
    int sum[SZ];
    int NT[SZ];
    
    // 0:live 1:dead
    
    void print(int x) { 
        for(int i = 0;i < n;i ++)
            printf("%d",x>>i&1);
        printf("");
    }
    
    
    void dfs(int d, int S, int nt) { 
        if(d == n) { 
            for(int i = 0;i <= m;i ++) { 
                G[i][S] = g[nt][i];
            }
            return ;
        }
    
        for(int i = 0;i <= m;i ++) { 
            for(int j = 0;j < a[d+1] && j <= i;j ++)
                g[nt+1][i] += g[nt][i-j] * C[i][j];
        }
        dfs(d+1,S,nt+1); // d is live
        for(int i = 0;i <= m;i ++) { 
            g[nt+1][i] = 0;
        }
        dfs(d+1,S^(1<<d),nt);
    }
    
    void init() { 
        C[0][0] = 1;
        for(int i = 1;i <= 100;i ++) { 
            C[i][0] = 1;
            for(int j = 1;j <= i;j ++) { 
                C[i][j] = C[i-1][j]+C[i-1][j-1];
            }
        }
    }
    
    bool isok(int i,int S) { 
        int nS = (1<<n)-S-1;
        return i >= sum[S] && sum[nS] - NT[S] >= i-sum[S];
    }
    
    int main() { 
        init();
        n = read(),m = read();
        for(int i = 1;i <= n;i ++) a[i] = read();
        for(int S = 0;S < (1<<n);S ++) { 
            for(int i = 0;i < n;i ++) { 
                if(S>>i&1)
                    sum[S] += a[i+1];
            }
        }
    
        g[0][0] = 1;
        dfs(0,0,0);
    
    
        for(int S = 0; S < (1<<n);S ++) {  // S,t: dead ns,nt: live
            int nt = 0;
            for(int i = 0;i < n;i ++) if(!(S>>i&1)) nt ++;
            NT[S] = nt;
        }
    
    
        // 0:live 1:dead
        double ans = 0;
        f[0][0] = 1;
        for(int S = 0; S < (1<<n);S ++) {  // 1,t: dead 0,nt: live
            int nt = 0;
            for(int i = 0;i < n;i ++) if(!(S>>i&1)) nt ++;
            int t = n - nt;
            int nS = (1<<n)-S-1;
            for(int i = 0;i < m;i ++) { 
                if(isok(i,S)) { 
                    double x = 1;
                    for(int j = 0;j < n;j ++) { 
                        if(!(S>>j&1)) {  // j is alive, make it dead
                            if(isok(i+1,S^(1<<j))) { 
                                double k = C[i-sum[S]][a[j+1]-1] / nt;
                                f[i+1][S^(1<<j)] += f[i][S] * k;
                            }
                        }
                    }
                    if(isok(i+1,S)) { 
                        f[i+1][S] += f[i][S] / nt;
                    }
                } else { 
                    f[i][S] = 0;
                }
            }
            if(m >= sum[S]) { 
                ans += f[m][S] * G[m-sum[S]][S] * t;
            }
        }
        printf("%.10f\n",(double)ans);
    }
    
    /* 15 100 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 */

## 7-7 字母排列问题 (10分) ##

> 从 m (0<m≤26) 个大写字母中任意选出 n (0<n≤m) 个字母排成一行，一共有多少种排列？ 请编写程序，输入 m 和 n，输出从A 开始的连续 m 个字母中任取 n 个字母的所有排列。  
> **要求**：每行输出一个排列，按字典序输出。  
> **输入样例**  
> 3 2  
> **输出样例**  
> AB  
> AC  
> BA  
> BC  
> CA  
> CB

#include<iostream>
    using namespace std;
    int m, n, ans[30], flag[30];//ans[]保存答案所选字母的序号，flag[]判断该字母是否被标记过 
    char s[30] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
    void search(int cur)
    { 	
    	if(cur == n){ //输出一个排列 
    		for(int i = 0; i < n; i++){ 
    			printf("%c", s[ans[i]]);
    		}
    		printf("\n");
    	}
    	else
        { 
    	    for(int k = 0; k < m; k++)//从m个字母中，每次选取一个未被标记过的，k每次从0开始判断，即可实现字典序排列 
            {  
    	        if(flag[k] == 0)//该字母未被标记时，进入下一层
                { 
    			    ans[cur] = k; //保存字母序号
    	        	flag[k] = 1;
    	        	search(cur + 1);
    	        	flag[k] = 0;
    			}
    		}
    	}
    }
    int main()
    { 
    	scanf("%d %d", &m, &n);
    	search(0);
    	return 0;
    }

## 7-8 子串 (10分) ##

> 现在有两个字符串A和B，请你给出子串B在文本A中出现的次数（可以非连续出现）。即：设A=\{a1…an\}，B=\{b1…bm\}，请给出有多少组不同的I=\{i1…im\}使得ai1=b1,ai2=b2…aim=bm。幸运的是，本题的子串长度确定为3。由于答案可能过大，请输出对10007取余后的结果。  
> **输入格式:**
> 
> 两行，每行一个字符串。第一行为字符串A（len<107），第二行为字符串B（len=3）。  
> **输出格式:**
> 
> 一行，一个整数，为子串出现次数mod10007。  
> **输入样例:**
> 
> aaabbbcccabc abc
> 
> **输出样例:**
> 
> 40

#include <bits/stdc++.h>
    typedef long long ll;
    using namespace std;
    int main()
    { 
        string a, b; int m = 0, n = 0; ll ans = 0;
    	cin >> a >> b;
        for (int i = 0; i < a.size(); i++)
        { 
            if (a[i] == b[2])
            { 
                for (int j = i - 1; j >= 0; j--)
                { 
                    if (a[j] == b[1])
                        n++;
                    else if (a[j] == b[0])
                        ans += n;
                }
                n = 0;
                ans %= 10007;
            }
        }
        cout<< ans<<endl;
    	return 0;
    }

## 7-9 刮刮彩票 (10分) ##

> “刮刮彩票”是一款网络游戏里面的一个小游戏。如图所示：
> 
> ![\-362960\_55cb6a89bf693.png][-362960_55cb6a89bf693.png]
> 
> 每次游戏玩家会拿到一张彩票，上面会有 9 个数字，分别为数字 1 到数字 9，数字各不重复，并以 3×3 的“九宫格”形式排布在彩票上。
> 
> 在游戏开始时能看见一个位置上的数字，其他位置上的数字均不可见。你可以选择三个位置的数字刮开，这样玩家就能看见四个位置上的数字了。最后玩家再从  
> 3 横、3 竖、2 斜共 8 个方向中挑选一个方向，方向上三个数字的和可根据下列表格进行兑奖，获得对应数额的金币。 数字合计 获得金币  
> 数字合计 获得金币 6 10,000 16 72 7 36 17 180 8 720 18 119 9 360  
> 19 36 10 80 20 306 11 252 21 1,080 12 108 22 144 13 72 23  
> 1,800 14 54 24 3,600 15 180
> 
> 现在请你写出一个模拟程序，模拟玩家的游戏过程。  
> **输入格式:**
> 
> 输入第一部分给出一张合法的彩票，即用 3 行 3 列给出 0 至 9 的数字。0  
> 表示的是这个位置上的数字初始时就能看见了，而不是彩票上的数字为 0。
> 
> 第二部给出玩家刮开的三个位置，分为三行，每行按格式 x y 给出玩家刮开的位置的行号和列号（题目中定义左上角的位置为第 1 行、第 1  
> 列。）。数据保证玩家不会重复刮开已刮开的数字。
> 
> 最后一部分给出玩家选择的方向，即一个整数： 1 至 3 表示选择横向的第一行、第二行、第三行，4 至 6  
> 表示纵向的第一列、第二列、第三列，7、8分别表示左上到右下的主对角线和右上到左下的副对角线。  
> **输出格式:**
> 
> 对于每一个刮开的操作，在一行中输出玩家能看到的数字。最后对于选择的方向，在一行中输出玩家获得的金币数量。  
> **输入样例:**
> 
> 1 2 3 4 5 6 7 8 0 1 1 2 2 2 3 7
> 
> 输出样例:
> 
> 1 5 6 180

#include<iostream>
    using namespace std;
    int main()
    { 
        int p[25];
        p[6]=10000,p[7]=36,p[8]=720,p[9]=360,
        p[10]=80,p[11]=252,p[12]=108,p[13]=72,
        p[14]=54,p[15]=180,p[16]=72,p[17]=180,
        p[18]=119,p[19]=36,p[20]=306,p[21]=1080,
        p[22]=144,p[23]=1800,p[24]=3600;
        int a[4][4],x1,y1,sum=0;
        for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
        { 
            cin>>a[i][j];
            sum+=a[i][j];
            if(a[i][j]==0)
            { 
                x1=i,y1=j;
            }
        }
        a[x1][y1]=45-sum;
        for(int i=1;i<=3;i++)
        { 
            int x,y;
            cin>>x>>y;
            cout<<a[x][y]<<endl;
        }
        int n;
        cin>>n;
        if(n==1)cout<<p[a[1][1]+a[1][2]+a[1][3]];
        else if(n==2)cout<<p[a[2][1]+a[2][2]+a[2][3]];
        else if(n==3)cout<<p[a[3][1]+a[3][2]+a[3][3]];
        else if(n==4)cout<<p[a[1][1]+a[2][1]+a[3][1]];
        else if(n==5)cout<<p[a[1][2]+a[2][2]+a[3][2]];
        else if(n==6)cout<<p[a[1][3]+a[2][3]+a[3][3]];
        else if(n==7)cout<<p[a[1][1]+a[2][2]+a[3][3]];
        else cout<<p[a[1][3]+a[2][2]+a[3][1]];
        cout<<endl;
    }

## 7-10 求所有N位的素数和 (10分) ##

> 输入一个正整数n(n>=2)，输出所有n位的素数和，如n=2，即输出的是10-99之间的所有素数的和。  
> **输入格式:**
> 
> 一个正整数n(n>=2)  
> **输出格式:**
> 
> 输出所有n位的素数和 输入样例:
> 
> 2
> 
> **输出样例:**
> 
> 10-99之间所有的素数和=1043

#include<iostream>
    #include<math.h>
    using namespace std;
    int prime(int n);
    int main()
    { 
        int n,sum=0;
        cin>>n;
        int l=pow(10,n-1),r=pow(10,n)-1;
        for(int i=l;i<=r;i++)
        { 
            sum+=prime(i);
        }
        printf("%d-%d之间所有的素数和=%d",l,r,sum);
    }
    int prime(int n)
    { 
        if(n<=1)return 0;
        else
        { 
            for(int i=2;i*i<=n;i++)
            { 
                if(n%i==0)return 0;
            }
            return n;
        }
    }

[Reno-the-Relicologist-300x414.png]: /images/20210827/5e63135e72844377b0ecce9018fcb863.png
[-362960_55cb6a89bf693.png]: /images/20210827/4ec8310abd95460aa096f030eb5f8ccc.png