Posted 05/03/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 239 words)

看起来比较舒服的矩阵乘法模板

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>

#define SIZE 4 
#define mod 10000

using namespace std;

struct MATRIX
{
    int mt[SIZE][SIZE];
    int x,y;
}ans,def;

int n;

inline MATRIX operator *(MATRIX a,MATRIX b)
{
    MATRIX c;
    memset(c.mt,0,sizeof c.mt);
    c.x=a.x; c.y=b.y;
    for(int i=1;i<=a.x;i++)
        for(int j=1;j<=b.y;j++)
            for(int k=1;k<=a.y;k++)
                c.mt[i][j]=(c.mt[i][j]+(a.mt[i][k]%mod)*(b.mt[k][j]%mod))%mod;
    return c;
}

inline MATRIX operator +(MATRIX a,MATRIX b)
{
    MATRIX c;
    memset(c.mt,0,sizeof c.mt);
    c.x=a.x; c.y=a.y;
    for(int i=1;i<=c.x;i++)
        for(int j=1;j<=c.y;j++)
            c.mt[i][j]=(a.mt[i][j]+b.mt[i][j])%mod;
    return c;
}

inline bool prt(MATRIX &c)
{
    for(int i=1;i<=c.x;i++)
    {
        for(int j=1;j<=c.y;j++) printf("%d ",c.mt[i][j]);
        puts("");
    }
}

void go()
{
    n-=2;
    def.mt[1][1]=def.mt[1][2]=def.mt[2][1]=1;
    def.mt[2][2]=0; def.x=def.y=2;
    ans.mt[1][1]=ans.mt[1][2]=ans.mt[2][1]=1; ans.mt[2][2]=0;
    ans.x=ans.y=2;
    
    while(n)
    {
        if(n&1) ans=ans*def;
        def=def*def;
        n>>=1;
    }
    printf("%d\n",ans.mt[1][1]);
}

int main()
{
    while(scanf("%d",&n))
    {
        if(n==-1) break;
        else if(n==0) puts("0");
        else if(n==1) puts("1");
        else go();
    }
    system("pause");
    return 0;
}

Posted 05/03/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programinga minute read (About 167 words)

ACM-ICPC Live Archive Regionals 2014 >> Asia - Kuala Lumpur 6811 - Irrigation Lines

参见：转载前页面

怎么读题时就没发现“每行每列各有一个水阀”？这是把问题转化成二分图模型的关键啊

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
 
const int MAXN = 110;
char graph[MAXN][MAXN];
bool visited[MAXN];
int nCase, cCase, use[MAXN], m, n;
 
void init() {
    memset(use, -1, sizeof(use));
}
 
void input() {
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; i++) {
        scanf("%s", graph[i]);
    }
}
 
bool find(int x) {
    for (int j = 0; j < n; j++) {
        if (graph[x][j] == '1' && !visited[j]) {
            visited[j] = true;
 
            if (use[j] == -1 || find(use[j])) {
                use[j] = x;
                return true;
            }
        }
    }
    return false;
}
 
int match() {
    int count = 0;
    for (int i = 0; i < m; i++) {
        memset(visited, false, sizeof(visited));
        if (find(i)) count++;
    }
    return count;
}
 
void solve() {
    printf("Case #%d: %d\n", ++cCase, match());
}
 
int main() {
    scanf("%d", &nCase);
    while (nCase--) {
        init();
        input();
        solve();
 
    }
    return 0;
}

Posted 04/25/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programinga minute read (About 173 words)

2015年浙江省大学生程序设计竞赛

像这样搞错映射关系，不是个很好的情况

#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))


using namespace std;


typedef long long LL;
const double pi = acos(-1.0);
const int maxn=1e4;
const int inf=99999999;
const double eps=1e-3;


int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};


int ans(int x)
{


  //  cout<<x<<endl ;
    if (x==-1) return 6;
    if (x==0) return 5;
    if (x==1) return 6;
    if (x==2) return 9;
    if (x==3) return 6;
    if (x==4) return 5;
    if (x==5) return 5;
    if (x==6) return 5;
    if (x==7) return 5;
    if (x==8) return 6;
}


int isleap(int y)
{
    if ((y%4==0&&y%100!=0) || y%400==0) return 366;
    else return 365;
}


int fun(int y,int m)
{
    if (m==2)
    {
        if ((y%4==0&&y%100!=0) || y%400==0) return 29;
        else return 28;
    }
    else return month[m];
}


int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int y;
        scanf("%d",&y);
        int day=0;
        for(int i=1928;i<y;i++)
            day+=isleap(i);
        for(int i=1;i<=4;i++)
            day+=fun(y,i);
        day+=1;
        //cout<<day<<' ';
        cout<<ans(day%7)<<endl;
        /*switch (day%7)
        {
        case 0:


        }*/
    }
    return 0;
}

Posted 04/11/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programinga few seconds read (About 11 words)

POJ 3070 矩阵乘法模板 - proverbs - 博客园

POJ 3070 矩阵乘法模板 - proverbs - 博客园.

Posted 04/11/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programinga few seconds read (About 12 words)

POJ 2887 Big String （块状数组） - Geo_2014 - 推酷

POJ 2887 Big String （块状数组） - Geo_2014 - 推酷.

Posted 04/11/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 447 words)

【转】核心网络—BestCoder需要注意的几个问题

核心网络—BestCoder需要注意的几个问题.

1.不能随意hack，hack成功有加分，但是hack失败也会扣分！
2.不要随意提交已经AC的题目，罚时是这样的：最后一次AC的之前所有提交（无论AC与否）均算作罚时！其中AC的标为Accepted(Past)，被hack掉的AC也会标为Accepted(Past)。
3.AC不代表真正的AC，比赛最后阶段有hack数据，如果被hack掉就不算AC。hack数据一般都是非常变态的输入，或者是大数据！有时候有些人刻意利用题目bug构造变态的数据导致全场无人AC……
4.hack时只能读别人的代码，无法复制，这是锻炼读代码的能力。
5.如果有一场比赛注册了，但是忘做了，只要没有该场比赛的提交记录就不会使Rating降低。
6.只有本场比赛进入前300才能使Rating升高，否则就降低。
7.ABCD四道题的难度是依次升高的，分数也是依次升高的，根据错的次数和AC时间而使所得分数不同。
8.比赛题目是民间的ACMer出的，如果发现题目中有大量的英语语法错误，请不要见怪。
9.比赛日期并非固定在周五或者周六或者周日，根据杭电oj的具体日程安排而定。比如，如果有网络赛，可能就要提前或者延后了。
10.最后你的很多AC的题目可能都会被hack掉，请不要见怪。
11.

以上错误我几乎都犯过……
O__O”…

Posted 04/11/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 359 words)

【Bestcoder

1001 － Rikka with string

Accepts: 395
Submissions: 2281
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
Problem Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

One day, Yuta got a string which contains n letters but Rikka lost it in accident. Now they want to recover the string. Yuta remembers that the string only contains lowercase letters and it is not a palindrome string. Unfortunately he cannot remember some letters. Can you help him recover the string?

It is too difficult for Rikka. Can you help her?
Input

This problem has multi test cases (no more than 20). For each test case, The first line contains a number n(1≤n≤1000). The next line contains an n-length string which only contains lowercase letters and ‘?’ – the place which Yuta is not sure.
Output

For each test cases print a n-length string – the string you come up with. In the case where more than one string exists, print the lexicographically ﬁrst one. In the case where no such string exists, output “QwQ”.
Sample Input

5
a?bb?
3
aaa

Sample Output

aabba
QwQ

WA得智商都被拉低了 QAQ

int dfs(int step,bool &state)//1:to check
{
    int res;
    if (step<m-1) res=dfs(step+1,state);
    int pos=n-vec[step]-1;
    cout<<step<<' '<<str[vec[step]]<<' '<<str[pos]<<endl;
    for(char ch='a';ch<='z';ch++)
        if (state&&str[pos]==ch)
        {
            if (ch<'z') continue;
            else return -1;//error
        }
        else
        {
            str[vec[step]]=ch;
            if (state&&str[pos]!='?'&&ch!=str[pos]) state=0;
            if (ch!=str[pos]) return 1;
        }
    return -1;
}

AC：

#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))

using namespace std;

typedef long long LL;
const double pi = acos(-1.0);
const int maxn=2e3;
const int inf=99999999;
const float eps=1e-3;

vector<int> vec;
int n,m;
char s[maxn],str[maxn];

int dfs(int step,bool &state)//1:to check
{

    int pos=n-vec[step]-1;
    for(char ch='a';ch<='z';ch++)
        {
            str[vec[step]]=ch;
            if (str[pos]!='?'&&ch!=str[pos]) {state=0;}
            if (step<m-1) dfs(step+1,state);
            if (state&&str[pos]!='?'&&ch!=str[pos]||!state) return 1;
        }

    return -1;
}

int main()
{

    while(~scanf("%d",&n))
    {
        vec.clear();
        scanf("%s",s);
        memcpy(str,s,sizeof(s));
        for(int i=0;i<n;i++)
            if (s[i]=='?')
                vec.push_back(i);
        m=vec.size();
        bool tmp=1;

        if (m>1||m==1&&!(n%2&&vec[0]==n/2))
        {
            if (dfs(0,tmp)>=0) puts(str);
            else puts("QwQ");
        }
        else
        {
            bool ans=1;
            for(int i=1;i<=strlen(s)/2;i++)
                if (s[i-1]!=s[strlen(s)-i])
                {
                    ans=0;break;
                }
            if (m==1&&n%2&&vec[0]==n/2) str[vec[0]]='a';
            puts(ans?"QwQ":str);
        }

    }
    return 0;
}

Posted 03/23/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing7 minutes read (About 1102 words)

［心痛］线段树或树状数组求逆序数

原文地址

线段树或树状数组求逆序数

求逆序数的方法有分治，归并，本文只介绍线段树或树状数组求逆序数的办法，众所周知，线段树和树状树可以用来解决区间操作问题，就是因为这两个算法区间操作的时间复杂度很低O(logN)，才让这种方法具有可行性。

首先先来看一个序列 6 1 2 7 3 4 8 5，此序列的逆序数为5+3+1=9。冒泡法可以直接枚举出逆序数，但是时间复杂度太高O(n^2)。冒泡排序的原理是枚举每一个数组，然后找出这个数后面有多少个数是小于这个数的，小于它逆序数+1。仔细想一下，如果我们不用枚举这个数后面的所有数，而是直接得到小于这个数的个数，那么效率将会大大提高。

总共有N个数，如何判断第i+1个数到最后一个数之间有多少个数小于第i个数呢？不妨假设有一个区间 [1,N]，只需要判断区间[i+1,N]之间有多少个数小于第i个数。如果我们把总区间初始化为0，然后把第i个数之前出现过的数都在相应的区间把它的值定为1，那么问题就转换成了[i+1,N]值的总和。再仔细想一下，区间[1,i]的值+区间[i+1,N]的值=区间[1,N]的值(i已经标记为1)，所以区间[i+1,N]值的总和等于N-[1,i]的值！因为总共有N个数，不是比它小就是比它(大或等于)。

现在问题已经转化成了区间问题，枚举每个数，然后查询这个数前面的区间值的总和， i-[1,i] 既为逆序数。

线段树预处理时间复杂度O(NlogN)，N次查询和N次插入的时间复杂度都为O(NlogN)，总的时间复杂度O(3*NlogN)

树状数组不用预处理，N次查询和N次插入的时间复杂度都为O(NlogN)，总的时间复杂度O(2*NlogN)

线段树:
 

// 线段树
#include <stdio .h>
#include <string .h>
#include <stdlib .h>
#define MAX 51000
#define MID(a,b) (a+b)>>1
#define R(a) (a< <1|1)
#define L(a) a<<1
typedef struct {
    int num,left,right;
}Node;
int ans[MAX];
Node Tree[MAX<<2];
int n;

void Build(int t,int l,int r)         //以1为根节点建立线段树
{
    int mid;
    Tree[t].left=l,Tree[t].right=r;
    if(Tree[t].left==Tree[t].right)
    {
        Tree[t].num=0;
        return ;
    }
    mid=MID(Tree[t].left,Tree[t].right);
    Build(L(t),l,mid);
    Build(R(t),mid+1,r);
}

void Insert(int t,int l,int r,int x)     //向以1为根节点的区间[l,r]插入数字1
{
    int mid;
    if(Tree[t].left==l&&Tree[t].right==r)
    {
        Tree[t].num+=x;
        return ;
    }
    mid=MID(Tree[t].left,Tree[t].right);
    if(l>mid)
    {
        Insert(R(t),l,r,x);
    }
    else if(r< =mid)
    {
        Insert(L(t),l,r,x);
    }
    else
    {
        Insert(L(t),l,mid,x);
        Insert(R(t),mid+1,r,x);
    }
    Tree[t].num=Tree[L(t)].num+Tree[R(t)].num;
}

int Query(int t,int l,int r)           //查询以1为根节点，区间[l,r]的和
{
    int mid;
    if(Tree[t].left==l&&Tree[t].right==r)
        return Tree[t].num;
    mid=MID(Tree[t].left,Tree[t].right);
    if(l>mid)
    {
        return Query(R(t),l,r);
    }
    else if(r<=mid)
    {
        return Query(L(t),l,r);
    }
    else
    {
        return Query(L(t),l,mid)+Query(R(t),mid+1,r);
    }
}


int main()
{
    int a,n,i,t;
    scanf("%d",&t);
    long long int k;
    while(t--)
    {
        scanf("%d",&n);
        memset(Tree,0,sizeof(Tree));  //初始化线段树
        Build(1,1,n);
        for(i=1;i<=n;i++)             //输入n个数
        {
            scanf("%d",&ans[i]);
        }
        for(i=1,k=0;i<=n;i++)
        {
            a=ans[i];
            Insert(1,a,a,1);          //把线段树[ans[i],ans[i]]区间的值插入为1
            k=k+(i-Query(1,1,a));     //查询区间[1,ans[i]]值的总和,逆序数等于i-[1,ans[i]]
        }
        printf("%lld\n",k);
    }
    return 0;
}

树状数组:

// 树状数组
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX 100010
int c[MAX],a[MAX],ans[MAX],n;

int Lowbit(int x)      //返回二进制最后一个1所表示的数
{
  return x&(-x);
}

void Updata(int x)     //向前更新
{
  while(x<=n)
  {
    c[x]++;
    x+=Lowbit(x);
  }
}

int Sum(int x)         //向后更新求和
{
  int sum=0;
  while(x>0)
  {
    sum+=c[x];
    x-=Lowbit(x);
  }
  return sum;
}

int main()
{
  int i,t,k;
    scanf("%d",&t);
  while(t--)
  {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
    {
      scanf("%d",&ans[i]);
    }
    memset(c,0,sizeof(c));        //初始化树状数组
    for(i=1,k=0;i<=n;i++)
    {
      Updata(ans[i]);         //向后更新节点ans[i].k
      k=k+(i-Sum(ans[i]));    //向前查询节点ans[i].k
    }
    printf("%d\n",k);
  }
  return 0;
}

Posted 03/22/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programinga few seconds read (About 25 words)

FFZU-ACM月赛不行了

线段树/树状数组的另一种用法不会，它的逆向问题更不会

Posted 03/15/2015Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPC / Programing5 minutes read (About 692 words)

【GDUT-ACM】大灌水

难以容忍的两个WA
Problem C

int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
        {
            priority_queue<LL,vector<LL>,greater<LL> > que;
            CLEAR(a);
            scanf("%d%d",&n,&m);
            for(int i=0;i<n;i++) scanf("%lld",&a[i]);
            sort(a,a+n);
            for(int i=1;i<=m;i++)
            {
                que.push(a[n-i]);
            }
            LL ans=a[n-1];
            for(int i=n-m-1;i>=0;i--)
            {
                LL k=que.top();
                que.pop();
                que.push(k+a[i]);
                ans=max(ans,k+a[i]);
            }
            printf("%lld\n",ans);
        }
    return 0;
}

Problem D

#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))
 
using namespace std;
 
typedef long long LL;
const double pi = acos(-1.0);
const int maxn=2e5;
const LL maxl=1e5+10;
const int inf=99999999;
const float eps=1e-3;
 
LL a[maxn];
bool vis[maxl];
int n,m;
vector<LL> vec;
 
void init();
void solve();
void outp();
 
void get_prime()
{
    vec.clear();
    CLEAR(vis);
    int k=0;
    for (int i = 2; i < maxl;i++)
        if(!vis[i])
        {
            k++;
            vec.push_back(i);
            for (int j = 1; i * j <= maxl; j++)
            {
            vis[i * j] = 1;
            }
        }
}
 
int getfac(LL n)
{
    if (n<2) return 0;
    int h=0,res=0;
    while(h<vec.size())
    {
        if (n%vec[h]==0) res++;
        while (n%vec[h]==0) n/=vec[h];
        h++;
    }
    return res;
}
 
LL pow2(LL n)
{
    if (n<=0) return 1;
    else if (n==1) return 2;
    else if (n&1)
    {
        int k=pow2((n-1)>>1);
        return (k*k)<<1;
    }
    else
    {
        int k=pow2(n>>1);
        return k*k;
    }
}
 
int main()
{
    get_prime();
    int T;
    LL n,m;
    scanf("%d",&T);
    while(T--)
        {
            scanf("%lld%lld",&n,&m);
            if (m%n) {printf("0\n");continue;}
            else if (n==1) {printf("1\n");continue;}
            LL t=m/n;
            //printf("%d\n",getfac(t));
            LL ans=pow2(getfac(t)-1);
            printf("%lld\n",ans);
        }
    return 0;
}
 
void solve()
{
}
 
void init()
{
 
}
 
void outp()
{
    printf("\n");
}
 
/**************************************************************
    Problem: 1113
    User: semprathlon
    Language: C++
    Result: Wrong Answer
****************************************************************/

=====================================
Problem F
罕见的PE，输出末尾不能有多余空格，防不胜防

#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))
 
using namespace std;
 
typedef long long LL;
const double pi = acos(-1.0);
const int maxn=200;
const int inf=99999999;
const float eps=1e-3;
 
int a[maxn];
 
void init();
void solve();
void outp();
 
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
        {
            CLEAR(a);
            scanf("%d%d",&n,&m);
            int mina=inf,h=0;
            for(int i=0;i<m;i++)
            {
                int k;
                scanf("%d",&k);
                if (k<mina)
                {
                    mina=k;
                    a[h++]=k;
                }
            }
            sort(a,a+h);
            int k=0;
            for(int i=1;i<=n;i++)
            {
                if (k<h-1&&a[k+1]<=i) k++;
                if (i<n) printf("%d ",a[k]);
                else printf("%d",a[k]);
            }
            puts("");
        }
    return 0;
}
 
void solve()
{
}
 
void init()
{
 
}
 
void outp()
{
    printf("\n");
}
 
/**************************************************************
    Problem: 1121
    User: semprathlon
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1488 kb
****************************************************************/

Problem G

int main()
{
    while(~scanf("%d",&n))
        {
            int k=n/3;
            printf("%d\n",(n%3)?2*k+n%3-1:2*k);
        }
    return 0;
}

Problem E
裸的并查集

const int maxn=2e5;
const int inf=99999999;
const float eps=1e-3;
 
int f[maxn];
int n,m;
 
int getf(int n)
{
    if (f[n]==n) return n;
    else return f[n]=getf(f[n]);
}
 
bool unite(int u,int v)
{
    int x=getf(u);
    int y=getf(v);
    if (x!=y)
    {
        f[ y ]=x;return 1;
    }
    else return 0;
}
 
 
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
        {
            CLEAR(f);
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++) f[i]=i;
            for(int i=1;i<=m;i++)
            {
                int u,v;
                scanf("%d%d",&u,&v);
                unite(u,v);
            }
            int ans=-1;
            for(int i=1;i<=n;i++)
                if (f[i]==i) ans++;
            printf("%d\n",ans);
        }
    return 0;
}
 
/**************************************************************
    Problem: 1118
    User: semprathlon
    Language: C++
    Result: Accepted
    Time:264 ms
    Memory:2264 kb
****************************************************************/

=====================
还有个来不及提交的！［个人原因，15：26才加入比赛
Problem H

const int maxn=2e4;
const int inf=99999999;
const float eps=1e-3;
const pair<int,int> p0=make_pair(0,0);

int a[maxn],f1[maxn],f2[maxn];
pair<int,int> g1[maxn],g2[maxn];

void init();
void solve();
void outp();


int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        CLEAR(a);
        CLEAR(f1);
        CLEAR(f2);
        CLEAR(g1);
        CLEAR(g2);
        scanf("%d",&a[1]);
        f1[1]=f2[1]=0;
        g1[1]=g2[1]=p0;
        for(int i=2;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if (f1[i-1]<f2[i-1])
            {
                g1[i]=make_pair(a[i],g1[i-1].second);
                g2[i]=make_pair(g1[i-1].first,a[i]);
                f1[i]=f1[i-1]+abs(a[i]-g1[i-1].first);
                f2[i]=f2[i-1]+abs(a[i]-g1[i-1].second);
            }
            else
            {
                g1[i]=make_pair(a[i],g2[i-1].second);
                g2[i]=make_pair(g2[i-1].first,a[i]);
                f1[i]=f1[i-1]+abs(a[i]-g2[i-1].first);
                f2[i]=f2[i-1]+abs(a[i]-g2[i-1].second);
            }

        }
        printf("%d\n",min(f1[n],f2[n]));
    }
}