zoj 3927 Programming Ability Test

題意：四個(gè)數(shù)的和大于等于80。這么招搖的廣告，為了廣告效應(yīng)也得是道水題~~~

#include
#include
#include
#include
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--){
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
if(a+b+c+d>=80)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}

zoj 3929 Deque and Balls

搬磚的地址： http://blog.csdn.net/doris1104/article/details/51126910
題意：每次等概率地往一個(gè)序列的左邊或右邊放一個(gè)球，問期望的相鄰逆序?qū)τ卸嗌賯€(gè)。
思考出發(fā)點(diǎn)：當(dāng)放入第 i 個(gè)球時(shí)，恰好在第 j 個(gè)球左邊/右邊的概率是多少？
稍微找一下規(guī)律就可以發(fā)現(xiàn)：i 號(hào)球
和 i – 1 號(hào)球相鄰的概率是 ?
和 i – 2 號(hào)球相鄰的概率是 ?
以此類推，一個(gè)例外是與 1 號(hào)球相鄰的概率和與 2 號(hào)球相鄰的概率是相同的
做法思路：維護(hù)一個(gè)數(shù)據(jù)結(jié)構(gòu)，用于查詢比 x 小的元素的概率之和是多少，再維護(hù)一個(gè)數(shù)據(jù)結(jié)構(gòu)，查詢比 x 大的元素的概率之和是多少，然后把查詢的結(jié)果加起來
既然如此，那就可以直接用一個(gè)數(shù)組，查詢 x 時(shí)，計(jì)算不等于 x 的概率就行了
最后答案會(huì)乘以 2^n，因此所有的概率都能用整數(shù)表示，別算錯(cuò)就行了

#include<bits/stdc++.h>  
#define ll long long  
#define mod 1000000007  
using namespace std;  

ll power[100005];
ll r[100005];
ll dp[100005];
int main(){
    power[0]=1;
    for(int i=1;i<=100000;i++){
        power[i]=(power[i-1]*2)%mod;
    }
    int t,n,a;
    cin>>t;
    while(t--){
        memset(r,0,sizeof(r));  
        memset(dp,0,sizeof(dp));
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a;
            dp[i]=(dp[i-1]*2+power[i-2]-r[a]+mod)%mod;
            if(i==1)
                r[a]=(r[a]+1)%mod;
            else
                r[a]=(r[a]+power[i-2])%mod;
        }
        cout<<dp[n]*2%mod<<endl;
    }
    return 0;
}

zoj 3930 Dice Notation

題意：可以直接看樣例的模擬題，但是要注意對換行符的處理。

#include<stdio.h>
#include<string.h>

char tmp[2000000+10],s[2000000+10];
char ans[2000000+10];
char u[2000000+10];
int  T,len,f;
int  g;

void init(){
    memset(tmp,0,sizeof(tmp));
    memset(ans,0,sizeof(ans));
    memset(s,0,sizeof(s));
    len=0;
    f=0;
}

void c(){
    for(int i=0;tmp[i];i++){
        if(tmp[i]=='d'||tmp[i]=='+'||tmp[i]=='-'||tmp[i]=='*'||tmp[i]=='/'||tmp[i]=='('
        ||tmp[i]==')'||(tmp[i]>='0'&&tmp[i]<='9'))
            s[len++]=tmp[i];
    }
}

void work(){
    int pre=0;
    int pos1,pos2;
    for(int i=0;s[i];i++){
        if(s[i]=='d'){
            pos1=i,pos2=i;
            for(int j=i+1;s[j];j++){
                if(s[j]>='0'&&s[j]<='9')
                    pos2=j;
                else 
                    break;
            }
            for(int j=i-1;j>=0;j--){
                if(s[j]>='0'&&s[j]<='9')
                    pos1=j;
                else
                    break;
            }
            int a=0;
            for(int j=pos1;j<=i-1;j++)
                a=a*10+s[j]-'0';
            for(int j=pre;j<pos1;j++)
                ans[f++]=s[j];
            pre=pos2+1;
            memset(u,0,sizeof(u));
            g=0;
            u[g++]='[';
            for(int j=i;j<=pos2;j++)
                u[g++]=s[j];
            u[g++]=']';
            if(a==0)
                a=1;
            if(a!=1)
                ans[f++]='(';
            for(int k=0;u[k];k++)
                ans[f++]=u[k];
            for(int j=1;j<=a-1;j++){
                ans[f++]='+';
                for(int k=0;u[k];k++)
                    ans[f++]=u[k];
            }
            if(a!=1)
                ans[f++]=')';
        }
    }
    for(int j=pre;s[j];j++)
        ans[f++]=s[j];
}

void print(){
    for(int i=0;ans[i];i++){
        if(ans[i]=='+'||ans[i]=='-'||ans[i]=='*'||ans[i]=='/')
            printf(" %c ",ans[i]);
        else
            printf("%c",ans[i]);
    }
    printf(" = [Result]\n");
}

int main(){
    scanf("%d",&T);
    getchar();
    while(T--){
        init();
        gets(tmp);
        c();
        work();
        print();
    }
    return 0;
}

zoj 3932 Handshakes

題意：貪心，當(dāng)前擁有最多朋友的人總能和進(jìn)來的人握手

#include <iostream>
#include <string> 
#include <cstdio>
#include <cstring>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;
int a[100005],sum[100005];
int main()
{
  int t,n,maxx;
  scanf("%d",&t);
  while(t--)
  {
      maxx=0;
      scanf("%d",&n);
      for(int i=1;i<=n;i++)
      {
          scanf("%d",&a[i]);
      }
      a[n+1]=0;
      sum[n+1]=0;
      for(int i=n;i>=1;i--)
      {
          if(a[i+1])
          {
              sum[i]=sum[i+1]+1;
          }
          else
              sum[i]=sum[i+1];
          if(a[i]+sum[i]>maxx)
              maxx=a[i]+sum[i];
      }
      printf("%d\n",maxx);
  }
  return 0;
}

zoj 3933 Team Formation

題意：有 n 個(gè)人，每個(gè)人屬于 0 組或是 1 組，現(xiàn)在想要組隊(duì)，每個(gè)隊(duì)伍必須是一個(gè) 0 組的人和一個(gè) 1 組的組隊(duì)，問在組隊(duì)數(shù)最多的情況下，隊(duì)伍中的女生數(shù)量最多能有多少個(gè)？
解題思路：比較直白的帶權(quán)匹配問題，權(quán)值要設(shè)大一點(diǎn)，可以用 KM 算法或是費(fèi)用流解決，稍微有一些卡模板效率，最好還是用 KM。

#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
using namespace std;
/* KM算法
 * 復(fù)雜度O(nx*nx*ny)
 * 求最大權(quán)匹配
 * 若求最小權(quán)匹配，可將權(quán)值取相反數(shù)，結(jié)果取相反數(shù)
 * 點(diǎn)的編號(hào)從0開始
 */
const int N = 505;
const int INF = 0x3f3f3f3f;
int nx,ny;//兩邊的點(diǎn)數(shù) nx,第一隊(duì)的個(gè)數(shù)，ny，第二隊(duì)的個(gè)數(shù)。注意 nx <= ny，否則會(huì)死循環(huán)。
int g[N][N];//二分圖描述  g[i][j],i屬于第一隊(duì)，j屬于第二隊(duì)。
int linker[N],lx[N],ly[N];//y中各點(diǎn)匹配狀態(tài)，x,y中的點(diǎn)標(biāo)號(hào)
int slack[N];
bool visx[N],visy[N];
bool DFS(int x)
{
    visx[x] = true;
    for(int y = 0; y < ny; y++)
    {
        if(visy[y])continue;
        int tmp = lx[x] + ly[y] - g[x][y];
        if(tmp == 0)
        {
            visy[y] = true;
            if(linker[y] == -1 || DFS(linker[y]))
            {
                linker[y] = x;
                return true;
            }
        }
        else if(slack[y] > tmp)
            slack[y] = tmp;
    }
    return false;
}
int KM()
{
    memset(linker,-1,sizeof(linker));
    memset(ly,0,sizeof(ly));
    for(int i = 0;i < nx;i++)
    {
        lx[i] = -INF;
        for(int j = 0;j < ny;j++)
            if(g[i][j] > lx[i])
                lx[i] = g[i][j];
    }
    for(int x = 0;x < nx;x++)
    {
        for(int i = 0;i < ny;i++)
            slack[i] = INF;
        while(true)
        {
            memset(visx,false,sizeof(visx));
            memset(visy,false,sizeof(visy));
            if(DFS(x))break;
            int d = INF;
            for(int i = 0;i < ny;i++)
                if(!visy[i] && d > slack[i])
                    d = slack[i];
            for(int i = 0;i < nx;i++)
                if(visx[i])
                    lx[i] -= d;
            for(int i = 0;i < ny;i++)
            {
                if(visy[i])ly[i] += d;
                else slack[i] -= d;
            }
        }
    }
    int res = 0;
    for(int i = 0;i < ny;i++)
        if(linker[i] != -1)
            res += g[linker[i]][i];
    return res;
}

int vis[505][505];
int main(){
    int t,n,a,m;
    cin>>t;
    while(t--){
        memset(linker,0,sizeof(linker));
        memset(g,0,sizeof(g));
        memset(vis,0,sizeof(vis));
        cin>>n;
        string Group,Sex;
        cin>>Group>>Sex;
        nx=ny=n;
        for(int i=0;i<n;i++){
            cin>>m;
            for (int j = 0; j < m; j++){
                cin >> a;
                vis[i][a - 1] = 1;
                vis[a - 1][i] = 1;
            }
            for(int j=0;j<n;j++){
                if(!vis[i][j]&&!vis[j][i]&&Group[i]!=Group[j]){
                    int ret=20000;
                    if(Sex[i]=='0') ret++;
                    if(Sex[j]=='0') ret++;
                    if(Group[i]=='0'&&Group[j]=='1') g[i][j]=ret;
                    else if (Group[i] == '1' && Group[j] == '0') g[j][i] = ret;
                }
            }
        }
        int res=KM();
        cout<<(res/20000)<<" "<<(res%10000)<<endl;
        for(int i=0;i<n;i++){
            if(linker[i]!=-1&&g[linker[i]][i]){
                cout << linker[i] + 1 << " " << i + 1 << endl;
            }
        }
    }
    return 0;
}

zoj 3935 2016

題意：既是三角形數(shù)又是六角形數(shù)且是閏年的數(shù)字

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
int T, n, m;

int main() {
    for (int i = 2016, j = 476; i <= 990528; i += j)
    {
        if (i % 400 == 0 || i % 100 != 0) printf("%d\n", i);
        j += 64;
    }
    return 0;
}