题目描述

blablabla

样例

blablabla

算法1

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int n;
int nums[N];
int sum[N];
int ans;
bool flag;
int dist=1e9;

void dfs(int u,int cur)
{
    if(flag)return;
    if(cur>sum[n]/2||sum[n]-2*(cur+sum[u])>dist)return ;
    if(u==0)
    {
        int d=sum[n]-cur-cur;
        if(d<dist)
        {
            dist=d;
            ans=cur;
            if(dist==1||dist==0)flag=true;
        }
        return ;
    }

    for(int i=u;i>=0;i--)dfs(i-1,cur+nums[i]);
}

int main()
{
    n=1;
    while(cin>>nums[n])n++;
    n--;
    sort(nums+1,nums+n+1);

    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+nums[i];

    dfs(n,0);

    if(sum[n]-ans>ans)cout<<sum[n]-ans<<" "<<ans<<endl;
    else cout<<ans<<" "<<sum[n]-ans<<endl;

    return 0;
}

算法2

(暴力枚举) $O(n^2)$

模板题改编的

C++ 代码

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

const int N=10010;

string a,b;
short dp[N][N];

int main(){
    cin>>a>>b;
    int n=a.size();
    int m=b.size();
    a=" "+a;
    b=" "+b;
    int res=0;
    for(int i=1;i<=n;i++){
        if(isdigit(a[i]))continue;
        for(int j=1;j<=m;j++){
            if(isdigit(b[j]))continue;

//因为求得是子串，所以如果a[i]!=b[j]那么当前得最长公共子串就断开了，所以没有dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(a[i]==b[j])dp[i][j]=max(dp[i][j],short(dp[i-1][j-1]+1));
            res=max(res,(int)dp[i][j]);
        }
    }


    cout<<res<<endl;
    return 0;
}

题目描述

关键点：
用的hash来进行月份转换；
通过暴力累加天数，来求周几。

算法1

C++ 代码

#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;


int yy[2],mm[2],dd[2];
int dm[2][13]={
    {0,31,28,31,30,31,30,31,31,30,31,30,31},//runyear
    {0,31,29,31,30,31,30,31,31,30,31,30,31},
};

string month[12]={
    "January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"
};
string week[7]={
    "Sunday","Monday", "Tuesday",  "Wednesday" ,  "Thursday" , "Friday", "Saturday"
};



bool isRunYear(int y){
    if(y%400==0||y%4==0&&y%100!=0)return true;
    return false;
}

void addDay(int &y,int &m,int &d){
    d++;
    if(d>dm[isRunYear(y)][m]){
        d=1;
        m+=1;
    }
    if(m>12){
        y+=1;
        m=1;
    }
}


bool isBefore(){
    if(yy[0]!=yy[1]){
        return yy[0]<yy[1];
    }
    else if(mm[0]!=mm[1]){
        return mm[0]<mm[1];
    }
    else {
        return dd[0]<dd[1];
    }
}


int main(){
    unordered_map<string,int>hash;
    for(int i=0;i<12;i++){
        hash[month[i]]=i+1;
    }

    string m;
    while(cin>>dd[1]>>m>>yy[1]){
        mm[1]=hash[m];
        yy[0]=1,mm[0]=1,dd[0]=1;
        int weekday=1;

        while(isBefore()){
            addDay(yy[0],mm[0],dd[0]);
            weekday=(weekday+1)%7;
        }

        cout<<week[weekday]<<endl;
    }
    system("pause");
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e6+10;

int primer[N];
bool st[N];
int n;

int get_p(int n){
    int cnt=0;
    for(int i=2;i<=n;i++){
        if(!st[i])primer[cnt++]=i;//如果没有被筛掉就是质数
        for(int j=0;primer[j]<=n/i;j++){
            st[i*primer[j]]=true;//是最小质因数的倍数筛掉
            if(i%primer[j]==0)break;//i%primer[j]==0,说明primerj是i的最小质因数，结束了，否则往后继续找到i的最小质因数
        }
    }
    return cnt;
}

int main(){
    cin>>n;
    int ans;
    ans=get_p(n);
    cout<<ans<<endl;
    system("pause");
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int n;
int a;

void func(int n){
    for(int i=2;i<=n/i;i++){
        if(n%i==0){
            int s=0;
            while(n%i==0)n/=i,s++;
            cout<<i<<" "<<s<<endl;

        }
    }
    if(n>1)cout<<n<<" "<<1<<endl;
}


int main(){
    cin>>n;
    while(n--){
        cin>>a;
        func(a);
        cout<<endl;
    }

    system("pause");
    return 0;
}

#include<iostream>
#include<algorithm>

using namespace std;

int n;
int x;

bool isValid(int x){
    if(x<2)return false;
    for(int i=2;i<=x/i;i++){
        if(x%i==0)return false;
    }
    return true;
}

int main(){
    cin>>n;
    while(n--){
        cin>>x;
        if(isValid(x))cout<<"Yes";
        else cout<<"No";
        cout<<endl;
    }
    return 0;
}

#include<iostream>

using namespace std;

const int N=1e5+10;

int n,m;
int p[N];

int find(int x){
    if(x!=p[x])p[x]=find(p[x]);
    else return x;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)p[i]=i;
    while(m--){
        char c;
        int a,b;
        cin>>c>>a>>b;
        int x=find(a),y=find(b);
        if(c=='M'){
            if(x==y)continue;
            else p[x]=y;
        }else if(c=='Q'){
            if(x==y)cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    system("pause");
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;

LL qmi(LL a,LL k,LL p){
    LL res=1%p;
    while(k){
        if(k&1)res=res*a%p;
        a=a*a%p;
        k>>=1;
    }
    return res%p;
}

int main(){
    int n;
    cin>>n;
    while(n--){
        LL a,b,c;
        cin>>a>>b>>c;
        cout<<qmi(a,b,c)<<endl;
    }
    system("pause");
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int N=2010,M=1e4+10;

int n,m;
int h[N],e[M],ne[M],w[M],idx;
int dist[N],cnt[N];
queue<int>q;
bool st[N];

void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

bool spfa(){
    for(int i=1;i<=n;i++){
        q.push(i);
        st[i]=true;
    }


    while(q.size()){
        int t=q.front();
        q.pop();
        st[t]=false;

        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n)return true;
                if(!st[j]){
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return false;
}



int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    if(spfa())cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    system("pause");
    return 0;
}

```#include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

const int N=1e5+10;

int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
queue[HTML_REMOVED]q;
bool st[N];

void add(int a,int b,int c){
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void spfa(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
q.push(1);
st[1]=true;

while(q.size()){
    int t=q.front();
    q.pop();
    st[t]=false;

    for(int i=h[t];i!=-1;i=ne[i]){
        int j=e[i];

        if(dist[j]>dist[t]+w[i]){
            dist[j]=dist[t]+w[i];
            if(!st[j]){
                st[j]=true;
                q.push(j);
            }
        }
    }
}

}

int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=0;i[HTML_REMOVED]>a>>b>>c;
add(a,b,c);
}
spfa();
if(dist[n]>=0x3f3f3f3f/2)cout<<”impossible”<<endl;
else cout<<dist[n]<<endl;

system("pause");
return 0;

}
```