第二届ACM山东省赛

A: Nim+Bash 博弈

Nim博弈可以看做只考虑取二进制化后的数的位数上的1,结合Bash就变成了从几堆中取相应的1

答案是 统计二进制位数,如果全部取模(3+1)等于0,则是必败态

#include<bits/stdc++.h>
using namespace std;
const int maxn=11000;

int a[maxn],N,T,K,max_tot;

int main(){
    scanf("%d",&T);
    while(T--){
        memset(a,0,sizeof(a));
        max_tot=0;
        scanf("%d",&N);
        for(int i=0;i<N;++i){
            scanf("%d",&K);
            int tot=0;
            while(K){
                if(K&1) a[tot++]++;
                else tot++;
                K>>=1;
            }
            max_tot=max(max_tot,tot);
        }
        //printf("max: %d\n",max_tot);
        bool flag=true;
        for(int i=0;i<max_tot;++i){
            if(a[i]%4){
                flag=false;
                break;
            }
        }
        printf(flag?"No\n":"Yes\n");
    }
    return 0;
}

B:排序模拟

#include<bits/stdc++.h>
using namespace std;

struct team{
    char name[40];
    bool all_girls;
    int solved;
    int pe;
    int id;

    bool operator<(const team& A) const{
        if(solved==A.solved){
            return pe>A.pe;
        }else return solved<A.solved;
    }
};

struct Name{
    char name[40];
    int id;
    bool operator<(const Name& A) const{
        return id<A.id;
    }
};

int T,kase=1;
int N,M;
char str[1000];
priority_queue<team> pt;
vector<Name> ans;

void init(){
    while(!pt.empty()) pt.pop();
    ans.clear();
}

team get_team(int id){
    char name[40];
    bool all_girls;
    int solved;
    int pe;
    team t;

    sscanf(str,"%s %d %d %d",name,&all_girls,&solved,&pe);
    strcpy(t.name,name);
    t.all_girls=all_girls;
    t.solved=solved;
    t.pe=pe;
    t.id=id;
    return t;
}

Name new_me(char str[40],int ind){
    Name me;
    strcpy(me.name,str);
    me.id=ind;
    return me;
}

void can(){
    bool has_girl=false;
    while(!pt.empty()){
        team a=pt.top();pt.pop();
        if(a.solved<=0) break;
        if(a.all_girls) has_girl=true;
        ans.push_back(new_me(a.name,a.id));
        M--;
        if(M==0)break;
    }
    if(M==0){
        if(!has_girl){
            while(!pt.empty()){
                team a=pt.top();pt.pop();
                if(a.solved<=0) break;
                if(a.all_girls){
                    ans.push_back(new_me(a.name,a.id));
                    break;
                }
            }
        }
    }
}

void cant(){
    while(!pt.empty()){
        team a=pt.top();pt.pop();
        ans.push_back(new_me(a.name,a.id));
    }
}

void print(){
    sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();++i){
        printf("%s\n",ans[i].name);
    }
    puts("");
}

int main(){
    scanf("%d",&T);
    while(T--){
        init();
        scanf("%d%d\n",&N,&M);
        int low=0;
        for(int i=0;i<N;++i){
            gets(str);
            team a=get_team(i);
            if(a.solved>=1) low++;
            pt.push(a);
        }
        printf("Case %d:\n",kase++);
        if(low>=M) can();
        else cant();
        print();
    }
    return 0;
}

C:水

#include<bits/stdc++.h>
using namespace std;
const int maxn=200;
char str[maxn];
int T;

int main(){
    scanf("%d",&T);
    while(T--){
        bool is=true;
        gets(str);
        int len=strlen(str);
        if(isalpha(str[0]) || str[0]=='_'){
            for(int i=1;i<len;++i){
                if(!(isalpha(str[i]) || isdigit(str[i]) || str[i]=='_')){
                    printf("No\n");
                    is=false;
                    break;
                }
            }
        }else{
            printf("No\n");
            is=false;
        }
        if(is) printf("Yes\n");
    }

    return 0;
}


D: 求组合数模,可以大数,可以打表

///1000*1000的数据直接打表就好
#include <iostream>
#include <string.h>
using namespace std;
const int mod=10000003;
const int N=1002;
int c[N][N];

void init()//递推打表
{
    memset(c,0,sizeof(c));
    c[0][0]=c[1][0]=c[1][1]=1;
    for(int i=2;i<N;i++)
    {
        c[i][i]=c[i][0]=1;
        for(int j=0;j<i;j++)
        {
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;//不会越界
        }
    }
}
int main()
{
    init();
    int k;cin>>k;
    int a,b;
    while(k--)
    {
        cin>>a>>b;
        cout<<c[a][b]<<endl;//直接输出
    }
}

E:快速幂模+数组模拟trie

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e6+7;

int mp[11][11][11];
char res[11][11][11];
char str[maxn];

ll mod_pow(ull x,ull n,int mod){
    ull res=1;
    while(n>0){
        if(n&1) res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}

void f(int id,int n){
    int ans=mod_pow(id,n,997);
    //cout<<ans<<endl;
    int cnt=0;
    int dt[3]={0,0,0};
    while(ans){
        dt[cnt++]=ans%10;
        ans/=10;
    }
    mp[dt[2]][dt[1]][dt[0]]++;
    res[dt[2]][dt[1]][dt[0]]=(char)id;
}

void init(int n){
    memset(mp,0,sizeof(mp));
    ///处理数字
    for(int i=0;i<10;++i)
        f('0'+i,n);
    ///处理lowalpha
    for(int i=0;i<27;++i)
        f('a'+i,n);
    ///处理upperalpha
    for(int i=0;i<27;++i)
        f('A'+i,n);
}

int main(){
    int T,K;
    scanf("%d",&T);
    while(T--){
        scanf("%d\n%s",&K,str);
        init(K);
        int len=strlen(str);
        if(len%3){
            printf("No Solution\n");
            continue;
        }
        bool flag=true;
        string ans;
        for(int i=0;i<len;i+=3){
            int x=str[i]-'0',y=str[i+1]-'0',z=str[i+2]-'0';
            //cout<<x<<y<<z<<mp[x][y][z]<<endl;
            if(mp[x][y][z]>1 || mp[x][y][z]==0){
                flag=false;
                break;
            }
            ans+=res[x][y][z];
        }
        if(flag) cout<<ans<<endl;
        else cout<<"No Solution"<<endl;
    }

    return 0;
}

I: 区间DP

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=1010;
typedef long long LL;
LL dp[maxn];
LL sum[maxn],num;
int T,N,M;


int main(){
    scanf("%d",&T);
    while(T--){
        sum[0]=0ll;
        dp[0]=0ll;
        scanf("%d%d",&N,&M);
        for(int i=1;i<=N;++i){
            scanf("%lld",&num);
            sum[i]=sum[i-1]+num;
            dp[i]=sum[i]*sum[i];
        }

        for(int i=2;i<=M;++i){
            ///枚举区间,j为i划分倒推的一维
            for(int j=N-M+i;j>=i;--j){
                for(int k=1;k<j;++k){
                    dp[j]=min(dp[j],dp[k]+(sum[j]-sum[k])*(sum[j]-sum[k]));
                }
            }
        }
        printf("%lld\n",dp[N]);
    }
    return 0;
}

POJ 2186

Tarjan

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int maxn=100000+10;
/*
  有n只牛,牛之间存在一些关系,比如a认为b很受欢迎
,b认为c很受欢迎,这样呢,a也会认为c很受欢迎,问根据
给出的关系,有多少头牛被其他所有的牛都认为是受欢迎的?

解:
  对于一个有向无环图来说,其中有且仅有一个点出度为零
,那么这个特殊的点,可以由其他任何点到达。那么接下来我
们直接对所给的图进行强连通分量划分,然后把每个强连通分
量看做一个点,判定出度为零的点有几个,如果有一个就输出
这个点对应的强连通分量含有的节点个数,否则为零。
*/
vector<int> G[maxn];
//lowlink[u] == 为u及其后代能追溯到的最早(最先被发现)的祖先节点v的pre[v]的值.
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;

int vis[maxn];

stack<int> S;
//邻接表存储图
void addAdge(int u,int v){
    ///如果点从1开始计数,这里改成-1即可
    G[u-1].push_back(v-1);
}

void dfs(int u){
    pre[u]=lowlink[u]= ++dfs_clock;
    //边dfs将点入栈边Tarjan
    S.push(u);
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if(!pre[v]){
            dfs(v);
            //回溯时计算lowlink数组
            lowlink[u]=min(lowlink[u],lowlink[v]);
        }else if(!sccno[v]){
            lowlink[u]=min(lowlink[u],pre[v]);
        }
    }
    if(lowlink[u]==pre[u]){
        scc_cnt++;
        for(;;){
            int x=S.top();S.pop();
            sccno[x]=scc_cnt;
            if(x==u)break;
        }
    }
}

void Tarjan(int n){
    dfs_clock=scc_cnt=0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    for(int i=0;i<n;++i){
        if(!pre[i]) dfs(i);
    }
}

int main(){
    //边数
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;++i){
        int u,v;
        cin>>u>>v;
        addAdge(u,v);
    }

    Tarjan(n);

    ///缩点,同一scc缩到同一点中
    for(int i=0;i<n;++i){
        for(int j=0;j<G[i].size();++j){
            ///如果i到G[i][j]这条边不在强连通分量中
            ///说明是一个连接外面的点
            if(sccno[i]!=sccno[G[i][j]]){
                vis[sccno[i]]++;
            }
        }
    }

    int sum=0,ans=0,cnt=0;
    for(int i=1;i<=scc_cnt;++i){
        if(!vis[i]){
            ///如果出度是0,则是一个边界点
            sum++;
            ans=i;
        }
    }
    ///如果只有一个点的话,代表存在一个万人敬仰团体
    if(sum==1){
        for(int i=0;i<n;++i){
            if(sccno[i]==ans){
                cnt++;
            }
        }
        printf("%d\n",cnt);
    }else{
        printf("0\n");
    }
    return 0;
}
/*
3 3
1 2
2 1
2 3

1
*/

第五届山东省ACM

D

类型: 线段树 区间更新

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100000*4;
typedef long long LL;
int N,Q,T;

LL lazy[maxn];
LL sum[maxn];
bool flag[maxn];

void init(){
    memset(lazy,0,sizeof(lazy));
    memset(sum,0,sizeof(sum));
    memset(flag,false,sizeof(flag));
}

void PushDown(int p,int m){
    if(flag[p]){
        lazy[p<<1]=lazy[p<<1|1]=0;
        sum[p<<1]=sum[p<<1|1]=sum[p]=0;
        flag[p<<1]=flag[p<<1|1]=true;
        flag[p]=false;
    }
    if(lazy[p]){
        lazy[p<<1]+=lazy[p];
        lazy[p<<1|1]+=lazy[p];
        sum[p<<1]+=(m-(m>>1))*lazy[p];
        sum[p<<1|1]+=(m>>1)*lazy[p];
        lazy[p]=0;
    }
}

void update(int p,int l,int r,int c,int L,int R){
    if(L<=l && r<=R){
        lazy[p]+=c;
        sum[p]+=(LL)(r-l+1)*c;
        return;
    }
    PushDown(p,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid) update(p<<1,l,mid,c,L,R);
    if(R>mid) update(p<<1|1,mid+1,r,c,L,R);
    sum[p]=sum[p<<1]+sum[p<<1|1];
}

LL Query(int p,int l,int r,int L,int R){
    if(L<=l && r<=R)
        return sum[p];
    PushDown(p,r-l+1);
    int mid=(l+r)>>1;
    LL ret=0;
    if(L<=mid) ret+=Query(p<<1,l,mid,L,R);
    if(R>mid) ret+=Query(p<<1|1,mid+1,r,L,R);
    return ret;
}

void setf(int p,int l,int r,int L,int R,int c){

    if(L<=l && r<=R){
        lazy[p]=0;
        sum[p]=0;
        flag[p]=true;
        return;
    }
    PushDown(p,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid) setf(p<<1,l,mid,L,R,c);
    if(R>mid) setf(p<<1|1,mid+1,r,L,R,c);
    sum[p]=sum[p<<1]+sum[p<<1|1];
}

int main(){
    cin>>T;
    while(T--){
        init();
        scanf("%d%d",&N,&Q);
        int t,l,r,last=0;
        LL ans=0;
        for(int i=1;i<=Q;++i){
            scanf("%d%d%d",&t,&l,&r);
            ///先更新全部区间的值
            update(1,1,N,t-last,1,N);
            ///然后查询所需区间内的和
            ans+=Query(1,1,N,l,r);
            ///最后将所需区间内的值置为0
            setf(1,1,N,l,r,0);
            last=t;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

词云: Python爬取国际时事

前置工具

python
wordcloud
jieba
BeautifulSoup
matplotlib
scipy

第一步: 爬取国际时事列表

待爬地址: http://m.sohu.com/cr/57/?page=1&v=2

首先我们可以观察到,每点击列表中的下一页时, page 会加一

然后我们就可以确认,想获取多少条信息,直接替换page属性的值即可

然后我们观察想要爬取的内容:

审查元素:

我们发现文本都是在 div(class=”bd3 pb1″) -> div -> p -> a 标签下的:

编写代码

爬取数据并保存在data.txt中:

# coding: utf-8

from wordcloud import WordCloud
import requests
from bs4 import BeautifulSoup
import re

def getHTMLText(url):
    try:
        r = requests.get(url)
        r.raise_for_status()
        r.encoding = r.apparent_encoding
        return r.text
    except:
        pass

def has_p_a(tag):
    pass

def getWannaData(stockURL,res):
    html = getHTMLText(stockURL)
    soup = BeautifulSoup(html,'html.parser')
    p = soup.find('div',class_="bd3 pb1").find_all('a')
    for q in p:
        res.append(q.text)

res = []
maxn = 100
for i in range(1,maxn):
    getWannaData('http://m.sohu.com/cr/57/?page='+str(i)+'&v=2',res)

file = open('data.txt','a+')
for q in res:
    file.write(q+'\n')

其中maxn是控制爬取多少页的

data.txt 部分内容:

第二步: 生成词云

前置

因为要进行中文分词,所以要用jieba
注意再打开data.txt编码问题
还有ttf不能保存在有中文的路径下

背景图片

我们选择 水伊布.png

生成词云

容我说一句,在中国相对封闭的网络环境中,已经可以看到世界如此的乱了,全部的词条大部分是消极的…看起来大规模战争结束的时间太久了…(还是说,世界就没有安宁过)

这张图可以找到安倍