https://citel.bjtu.edu.cn/acm/oj/problem/1841

Problem A. QQ等级

时间限制 1000 ms

内存限制 64 MB

题目描述

SonaXiao 以前对QQ等级特别在意，整天挂着QQ为了升等级，还经常和别人比等级高低。

QQ等级的规则是：1个星星是1级，4个星星可以变成1个月亮（4级），4个月亮可以变成1个太阳（16级），4个太阳可以变成1个皇冠（64级）。再往上不知道有没有了，反正 SonaXiao 是没见过。

现在告诉你QQ等级，你能知道他的具体图标表示吗？

输入数据

第一行为一个整数 t (1≤t≤100)

，表示数据的组数。接下来对于每组数据：

第一行为一个整数 n (1≤n≤255)

，表示询问的QQ等级。

输出数据

对于每组数据，输出一行： 第一行为一个字符串，表示对应的QQ等级图标。

其中*代表星星，^代表月亮，@代表太阳，~代表皇冠。 图标应按其表示的等级从高到低排序。

样例输入

2249

样例输出

**@@@*

样例说明

请注意输出的合法性，例如，当 n=5

时，应该输出 ^*（一个月亮一个星星），而不是 *****（五个星星），*^ 也是不合法的。

 

 

---

【分析】：按照题意皇冠太阳月亮星星分别代表四进制的四位(逢四进一).

【代码】：

#include 
      
       using namespace std;#define ll long longint main(){   int t,n,ans,res;   cin>>t;   while(t--)   {       cin>>n;        if(n>=64) {            ans=n/64;            n%=64;           //  printf("ans=%d n=%d\n",ans,n);          while(ans--){                printf("~");            }        }        if(n>=16&&n<64){            ans=n/16;            n%=16;           // printf("ans=%d n=%d\n",ans,n);            while(ans--){                printf("@");            }        }        if(n>=4&&n<16){            ans=n/4;            n%=4;             //printf("ans=%d n=%d\n",ans,n);            while(ans--){                printf("^");            }        }        if(n>=1&&n<4){            ans=n/1;            n%=1;           // printf("ans=%d n=%d\n",ans,n);             while(ans--){                printf("*");            }        }    printf("\n");   }}
      

 

【同类】：

 

---

 

Problem B. 上三角矩阵的和

时间限制 1000 ms

内存限制 64 MB

题目描述

输出数据

对于每组数据，输出一行：

第一行为一个整数，表示上三角矩阵所有元素的和。

样例输入

221 132 3 4

样例输出

355 【分析】：矩阵中第i行的和为ai*(ai+...+an).枚举每一行并使用前缀和处理求和式即可. 注意：本题需要使用long long. 本题根据矩阵的性质可以推出公式((a1+…an)^2+(a1^2+…an^2))/2. 【代码】：

#include
       
        using namespace std;#define ll long longconst int N=1e6;ll t,n,a[N],sum[N],ans;int main(){    cin>>t;    while(t--){        memset(sum,0,sizeof(sum));        ans=0;        cin>>n;        for(int i=0;i
        
         >a[i];            sum[i]=sum[i-1]+a[i];        }        for(int i=0;i
        
       

 

---

 

Problem C. hwf的数列 待补

【官方】：

用ai[]表示用前i个数组合出的前n大是多少.

先用ai-1[]的前n大数据组合第i个数,一共n^2个,把它们排序,只取前n个即可.

理论共有2^n种组合,但我们利用贪心把前n个的组合控制在n个,即可省下冗余的计算,理论复杂度n^2.

本题需要使用long long.

本题也可使用堆结构存取数据.

---

Problem D. hwf吃披萨

时间限制 1000 ms

内存限制 64 MB

题目描述

hwf 是一个非常喜欢吃披萨的人。某天，天上掉下了一张披萨，被 hwf 和高老师看到了。

高老师把披萨分成了 n

份, 第 i 份的角度为 ai。为了公平起见，他们决定由 hwf 把 n

份披萨分成两堆，然后高老师肯定会挑一堆角度和多的，hwf 拿剩下的一堆。hwf 想吃到尽可能多的披萨，但是 hwf 的心思已经全在吃披萨上了。

快帮助 hwf，告诉他最多能吃到多少披萨吧！

输入数据

第一行为一个整数 t (1≤t≤500)

，表示数据的组数。接下来对于每组数据：

第一行有一个整数 n (2≤n≤360)，表示披萨被分成的份数。

第二行有 n 个整数 a1,a2,…,an (1≤ai<360)，分别表示第 i

份披萨的角度。

保证 ∑ni=1ai=360

 

输出数据

对于每组数据，输出一行：

第一行为一个整数，表示hwf最多可以吃到披萨的角度数。

样例输入

2410 130 170 503200 60 100

样例输出

180160 【分析】：01背包。用aij表示只用前i块披萨能否拼出角度j.两重循环枚举ij的所有情况.最后从前n块披萨,角度180向下找到第一个可行的角度即可. 【代码】：

#include
        
         using namespace std;const int M = 505;int w[M],sum;int dp[M];int main(){    int n;    int t;    cin>>t;    while(t--){    cin>>n;    sum = 0;    memset(dp, 0, sizeof(dp));    for (int i = 0; i < n; i++) {        scanf("%d", &w[i]);        sum += w[i];    }    for (int i = 0; i < n; i++)        for (int j = sum/2; j >= w[i]; j--)            dp[j] = max(dp[j], dp[j-w[i]] + w[i]);        printf("%d\n",min( sum - dp[sum/2], dp[sum/2]));    }    return 0;}
        

 

---

Problem E. 安全的密码

时间限制 1000 ms

内存限制 64 MB

题目描述

众所周知，密码安全是互联网时代人们最为关心的事情之一。而 RSA 公钥加密算法是目前最有影响力和最常用的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击。

其实 RSA 公钥加密算法的原理并不复杂，它基于一个十分简单的数论事实：将两个大素数相乘十分容易，而想要对其乘积进行质因数分解却极其困难，因此可以将乘积公开作为加密密钥。

所以 RSA 算法很重要的一个过程就是得到两个大素数相乘结果。

wchhlbt 和 Lazy_sheep 想要模拟一下 RSA 算法的加密过程。现在 wchhlbt拿到了 Lazy_sheep 提供的一份素数相乘的结果，但是 Lazy_sheep 因为别的事情计算的并不认真。 所以 wchhlbt 希望你来帮他判断这些数据的正确性。

输入数据

第一行为一个整数 t (1≤t≤1000)

，表示数据的组数。接下来对于每组数据：

第一行为一个整数 n (2≤n≤2×109)

。

输出数据

对于每组数据，输出一行：

如果这个数可以分解为两个素数乘积，输出YES，否则输出NO。

样例输入

46835121

样例输出

YESNOYESYES 【分析】： 用埃氏筛法或暴力处理出小于等于sqrt(n)的小素数m. 暴力尝试n能否整除某个m. 如果可以整除,则暴力判断n/m是否为素数.若是,则m,n/m是一组解. 暴力判断某个数是否为素数需要sqrt()的时间. 【代码】：

#include 
         
          using namespace std;#define ll long longconst int N=1e5+7;int a[10000],c,n,t;int main(){   cin>>t;   while(t--)   {       cin>>n;       c=0;       for(int i=2;i<=n;i++){        while(n%i==0){            a[c++]=i;            n/=i;        }       }       if(c==2) puts("YES");       else puts("NO");   }}
         

 

 

#include 
         
          using namespace std;#define ll long longconst int N=1e5+7;int a[10000],c,n,t;int check(int n){    for(int i=2;i*i<=n;i++) //注意是i*i《 n        if(n%i==0)            return 0;    return 1;}int main(){   cin>>t;   while(t--)   {       cin>>n;       int flag=0;       for(int i=2; i*i<=n && !flag; i++){            if(n%i==0 && check(i) && check(n/i))                flag=1;       }       puts(flag?"YES":"NO");   }}
         

 

---

Problem F. Infinity的装备 DFS+状压DP 待补

【官方】：

先以每个武器作为起点BFS处理出每两个点之间的距离,并建图.

用n位二进制数k表示每把武器是否取得的状态,a[k]记录完成这种状态需要的最小时间.

对于每种状态dp地处理下一种可能的状态,并取最优值即可.

最后答案是a[2^(n+1)-1].

---

Problem G. hwf的课表

时间限制 1000 ms

内存限制 64 MB

题目描述

在北京交通大学，每位同学每天最多上6节课：上午2节，中午1节，下午2节，晚上1节。 hwf 觉得所有的课都很有趣，但是同一时间不能有冲突课程。 hwf 想尽可能地多选课，那么 hwf 一周最多能选多少节课？

输入数据

第一行为一个整数 t (1≤t≤100)

，表示数据的组数。接下来对于每组数据：

第一行为一个整数 n (1≤n≤100)，表示所有可选的课程数。

接下来 n 行，每行有两个整数 a,b (1≤a≤7,1≤b≤6)，表示星期 a 的第 b

节有一门课可以选。

输出数据

对于每组数据，输出一行：

第一行为一个整数，表示 hwf 一周最多能选的课程数。

样例输入

131 11 21 1

样例输出

2 【分析】： 用aij记录第i天第j节能否选上课. 依次处理选择每个课程,最后统计每门课能否选择即可. 【代码】：

#include 
          
           using namespace std;#define ll long longconst int N=1e5+10;set< pair
           
             >st;int main(){   int t,n,a,b;   cin>>t;   while(t--)   {       st.clear();       cin>>n;       for(int i=0;i
            
             >a>>b;         st.insert(make_pair(a,b));       }       printf("%d\n",st.size());   }}
            
           
          

 

---

Problem H. hwf的安慰

时间限制 1000 ms

内存限制 64 MB

题目描述

期末考试的成绩下来了，好多同学都低于平均分，班里哇声一片……

作为班级核心成员，hwf 这时出来安慰大家：不要看平均分，那都是 dalao 们拉上去的，我们要看中位数！

每门考试有 n

个人参加，分数分别为 a1,a2,…,an

， 求每门考试所有同学得分的中位数。

输入数据

第一行为一个整数 t (1≤t≤100)

，表示数据的组数。接下来对于每组数据：

第一行为一个整数 n (1≤n≤500)，表示参加考试的人数。

第二行有 n 个整数 a1,a2,…an (0≤ai≤100)

，表示每个人的成绩。

输出数据

对于每组数据，输出一行：

第一行为一个实数，表示这门科目的成绩得分中位数（保留一位小数）。

样例输入

2298 100299 100

样例输出

99.099.5 【分析】：对所有成绩进行排序.如果奇数个人输出中间的数,偶数个人输出中间两个数的平均值即可. 【代码】：

#include 
           
            using namespace std;#define ll long longint main(){   int t,n,m;   double a[1050];   cin>>t;   while(t--)   {       cin>>n;       m=n/2;       for(int i=0;i
            
             >a[i];       }       sort(a,a+n);       if(n%2==1)        printf("%.1f\n",a[m]);       else        printf("%.1f\n",(a[m]+a[m-1])/2.0);   }}
            
           

 

---

Problem I. hwf的防AK题

时间限制 1000 ms

内存限制 64 MB

题目描述

众所周知，hwf 是出了名的菜，于是他决定在新生赛出一道非常非常非常难的防 AK（all killed）题来证明自己。于是他出了这道题。

求给定的字符串中有几个AK （区分大小写）。

输入数据

第一行为一个整数 t (2≤t≤10)

，表示数据的组数。接下来对于每组数据：

第一行为一个仅由大小写字母组成的字符串 s (2≤|s|≤105)

。

输出数据

对于每组数据，输出一行：

第一行为一个整数，表示这个字符串中AK个数。

样例输入

3gaolaoshishiwomendehongtaiyangTingShuoyouDalaoyaoAKlejiayouAKAKAK

样例输出

013 【分析】：读入字符串,统计每两个相邻的位置是否为AK,并记录个数即可. 【代码】：

#include 
            
             using namespace std;#define ll long longconst int N=1e5+10;int main(){   int t,n,cnt;   char s[N];   cin>>t;   while(t--)   {       cnt=0;       cin>>s;       n=strlen(s);       for(int i=0;i