7-26测试

问题 A: 谜题

时间限制: 1 Sec 内存限制: 128 MB
提交: 94 解决: 50
[提交][状态][讨论版]

题目描述

输入

一行一个数字N（N<=99）

输出

如果能，输出“YES”；否则输出“XLSB”;

样例输入

样例输出

YES

提示

【数据规模】

对于10%的数据，N<=1;

对于20%的数据，N<=3;

对于50%的数据，N<=4;

对于100%的数据1<=N<=99;

水题~~N<=4可以否则不行。判断末尾数字就知道。

选修课

时间限制: 1 Sec 内存限制: 128 MB
提交: 174 解决: 63
[提交][状态][讨论版]

题目描述

温州中学开放了许多选修课，每节选修课都属于一种种类。精力旺盛的黄小龙同学想要尽可能多的参加选修课，但是他只能选择M种种类的课程。当然，对于他所选的种类，他会去上所有该种类的课。现在他想知道他最多能上几节选修课，以及上最多选修课的方案数。

两种方案被认为不同当且仅当一种方案中存在另一种方案所没有的选修课。

输入

第一行一个只由小写字母组成，长度为N的字符串。表示有N节选修课，以及每节选修课的种类。

第二行一个正整数M。

输出

输出一行，两个用空格隔开的正整数，分别表示最多选修课数量和方案数。

样例输入

abcde
1


ababac
2

样例输出

1 5

5 1

提示

【数据规模】

对于30%的数据，M==1;

对于另外30%的数据，每种种类的选修课最多只有一节;

对于100%的数据1<=M<=26、1<=N<=100000;

模拟题，求C直接乘，水过。

#include<cstdio> 
#include<cstdlib> 
#include<cstring> 
#include<algorithm> 
using namespace std; 
typedef long long ll; 
bool cmp(int a,int b) 
    {return a>b;} 
ll calc(int a,int b){ 
    ll ans=1; 
    if (a>b/2)a=b-a; 
    for(int i=b;i>=(b-a+1);i--)ans*=(ll)i; 
    for(int i=1;i<=a;i++)ans/=(ll)i; 
    return ans; 
} 
int main(){ 
    char A[100010]; 
    ll st[30],m,ans=0,ans1=0; 
    scanf("%s",A); 
    int len=strlen(A); 
    for(int i=0;i<len;i++){ 
        st[A[i]-'a']++; 
    } 
    sort(st,st+26,cmp); 
    scanf("%lld",&m); 
    for(int i=0;i<m;i++){ 
        ans1+=st[i]; 
    } 
    int l=m-1,r=m-1; 
    while(l>0&&st[l-1]==st[m-1]) l--; 
    while(r<25&&st[r+1]==st[m-1]) r++; 
    ans=calc(m-l,r-l+1); 
    printf("%lld %lld",ans1,ans); 
}

宿管有一套神奇的控制系统来控制寝室的灯的开关：

共有N盏灯，标号为1到N，有M个标有不同质数的开关，开关可以控制所有标号为其标号倍数的灯，按一次开关，所有其控制的灭着的灯都点亮，所有其控制的亮着的灯将熄灭。现在，宿管可以无限的按所有开关，所有灯初始状态为熄灭，请求出最多能点亮几盏灯。

输入

输入有多组数据，第一行一个正整数T表示数据组数。

每组数据第一行两个整数N，M。

第二行M个不同的质数表示开关上的标号，保证所有标号<=N。

输出

对于每组数据输出一行一个整数表示最多亮灯数。

样例输入

样例输出

提示

【数据范围】

对于50%的数据,N<=15;

对于100%的数据，T<=10,N<=1000。

dfs题，对于大于等于sqrt（n）的枚举即可（不会互相影响）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath> 
#include<cstring> 
using namespace std;
int prime[102500],answer,n,m,k;
bool flag[102500];
void debug()
{
    for(int i=1;i<=n;i++)
    cout<<flag[i]<<' ';
    cout<<endl; 
}
void dfs(int p)
{
    if(p>k)
    {
        int ans=0;
        for(int i=1;i<=n;i++)
        if(flag[i]) ans++;
        for(int i=k+1;i<=m;i++)
        {
            int num=0;
            for(int j=1;j*prime[i]<=n;j++)
                {
                    if(!flag[j*prime[i]]) num++;else num--;
                    flag[j*prime[i]]^=1;
                }
            if(num>0) ans+=num;    
        }
        answer=max(answer,ans);    
        //debug();
        return;
    }
    for(int j=1;j*prime[p]<=n;j++)
    flag[j*prime[p]]^=1;
    dfs(p+1);
    for(int j=1;j*prime[p]<=n;j++)
    flag[j*prime[p]]^=1;
    dfs(p+1);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {    
        answer=0; 
        memset(flag,0,sizeof(flag));
        scanf("%d %d",&n,&m);
        for(int i=1;i<=m;i++)
        scanf("%d",&prime[i]);
        sort(prime+1,prime+1+m);
        int devide=sqrt(n);
        for(k=m;prime[k]>devide;k--);
        dfs(1);
        cout<<answer<<endl;
    }
}

感谢HK大佬和P王的挑错