• 13967708449
  • 1322284500@qq.com

Category Archivetopcoder

topcoder SRM 576 Div2 1000

00:00/00:00

1000:CharacterBoard2

题意:

给你一个字符组成的矩阵,这是从一个大矩阵里面截取出来的,大矩阵的最左上角坐标为(0,0),然后大矩阵是由一个连续长串经过不停的循环一行一行得排列出来的,已知这个长串的长度小于这个矩阵的宽度。。。然后问你符合条件的长串有几种。。。

分析:

已知这个长串的宽度是10000,然后这个小矩阵的大小也是50*50,然后我们可以直接暴力枚举长度然后暴力验证就好了。。。

代码:


int ans[10010]; int CharacterBoard2::countGenerators(vector <string> fragment, int W, int i0, int j0) { LL anss=0; for(int cas=1;cas<=W;cas++) { memset(ans,0,sizeof(ans)); int flag=0; int nowx=0+i0; int nowy=0+j0; int siz=fragment.size(); for(int j=0;j<siz;j++) { string now=fragment[j]; for(int i=nowy;i<nowy+now.size();i++) { int zz=nowx*W+i; zz%=cas; if(ans[zz]!=now[i-nowy]&&ans[zz]!=0) {flag=1;break;} else ans[zz]=now[i-nowy]; } if(flag==1) break; nowx++; } if(flag==0) { LL ret=1; for(int i=0;i<cas;i++) if(ans[i]==0) ret=((ret*26)%mod+mod)%mod; anss=((anss+ret)%mod+mod)%mod; } } return anss; }

topcoder SRM 574 Div1 250+500

00:00/00:00

250 : TheNumberGame

题意 :

给你两个数,两个人轮流操作,每次你可以把当前数反转或者除以10,然后给你的数字在int范围内,然后问你在500步内你可以把数字变成和另一个数相同,则你获胜。。。

分析 :

这里有一个非常简单的结论,我们只需要判断数字b是否在a中出现就好啦,正反都要判断,为什么自己想。。。

代码 :

int a[18],b[18],c[18];
string TheNumberGame::determineOutcome(int A, int B) 
{
    int ans=0;
    int lena=0,lenb=0;
    while(A)
        a[++lena]=A%10,A/=10;
    while(B)
        b[++lenb]=B%10,B/=10;
    for(int i=1;i<=lenb;i++)
        c[i]=b[lenb-i+1];
    for(int i=1;i<=lena-lenb+1;i++)
    {
        int zz=1;
        for(int j=1;j<=lenb;j++)
            if(a[i+j-1]!=b[j]){zz=0;break;}
        if(zz==1){ans=1;break;}
    }
    for(int i=1;i<=lena-lenb+1;i++)
    {
        int zz=1;
        for(int j=1;j<=lenb;j++)
            if(a[i+j-1]!=c[j]){zz=0;break;}
        if(zz==1){ans=1;break;}
    }
    if(ans==1)
        return "Manao wins";
    else return "Manao loses";
}

500:PolygonTraversal

该题就是Div2 1000的升级版,数据范围由13变成18,一样写就好啦,一算极限数据大概1.6亿,因为是TC所以能过。。。

代码 :


LL dp[1<<18][19]; vector <int> show[19]; void init(int now, const vector<int> & vec) { for(int i=0;i<=now;i++) show[i].clear(); for(int i=0;i<(1<<now);i++) show[__builtin_popcount(i)].push_back(i); memset(dp,0,sizeof(dp)); int start=0; for(int i=0;i<vec.size();i++) start|=(1<<(vec[i]-1)); show[vec.size()].clear(); show[vec.size()].push_back(start); dp[start][vec[vec.size()-1]-1]=1; } long long PolygonTraversal::count(int N, vector <int> points) { init(N,points); for(int i=points.size();i<=N;i++) { int siz=show[i].size(); for(int j=0;j<siz;j++) { int now=show[i][j]; for(int k=0;k<N;k++) { if(now&(1<<k)==0||!dp[now][k]) continue; for(int l=0;l<N;l++) { if(now&(1<<l)) continue; int flag1 = 0, flag2 = 0; int lb = min(k, l) + 1, ub = max(k, l) - 1; for (int ri = 0; ri < N; ri++) if (now >> ri & 1) { if (lb <= ri && ri <= ub) flag1 = 1; else if (ri < lb - 1 || ri > ub + 1) flag2 = 1; } int flag = flag1 & flag2; if(flag==1) dp[now|(1<<l)][l]+=dp[now][k]; } } } } LL ans=0,zz=points[0]-1; for(int i=0;i<N;i++) { if(i==(zz+N-1)%N||i==(zz+N+1)%N||i==zz) continue; ans+=dp[(1<<N)-1][i]; } return ans; }

topcoder SRM 574 Div 2 1000

PolygonTraversal2

题意 :

给你一个n个节点的正n边形,然后你有已经走了几步,你要接着走下去,每一步是连接两个节点,你走的每一步都要和之前的走过的线相交,最后一步回到起点。。。问有几种方案。。。

分析 :

因为n小于13,所以直接状压一下,然后枚举最后一步走到的点,然后枚举一个可以到达的点走下去。如何判断两个点的连线会和之前的线相交呢,我们只要满足这两个点把图形分成的两部分都有走过的点就好啦。。。

代码 :

int dp[1<<14][15];
vector <int> show[15];
void init(int now, const vector<int> & vec)
{
    for(int i=0;i<=now;i++)
        show[i].clear();
    for(int i=0;i<(1<<now);i++)
        show[__builtin_popcount(i)].push_back(i);
    memset(dp,0,sizeof(dp));
    int start=0;
    for(int i=0;i<vec.size();i++)
        start|=(1<<(vec[i]-1));
    show[vec.size()].clear();
    show[vec.size()].push_back(start);
    dp[start][vec[vec.size()-1]-1]=1;
}
int PolygonTraversal2::count(int N, vector <int> points) 
{
    init(N,points);
    for(int i=points.size();i<=N;i++)
    {       
        int siz=show[i].size();
        for(int j=0;j<siz;j++)
        {
            int now=show[i][j];
            for(int k=0;k<N;k++)
            {
                if(now&(1<<k)==0||!dp[now][k])
                    continue;
                for(int l=0;l<N;l++)
                {
                    if(now&(1<<l))
                        continue;
                    int flag1 = 0, flag2 = 0;
                    int lb = min(k, l) + 1, ub = max(k, l) - 1;
                    for (int ri = 0; ri < N; ri++)
                        if (now >> ri & 1) {
                            if (lb <= ri && ri <= ub) flag1 = 1;
                            else if (ri < lb - 1 || ri > ub + 1) flag2 = 1;
                        }
                    int flag = flag1 & flag2;
                    if(flag==1)
                        dp[now|(1<<l)][l]+=dp[now][k];
                }
            }
        }
    }
    int ans=0,zz=points[0]-1;
    for(int i=0;i<N;i++)
    {
        if(i==(zz+N-1)%N||i==(zz+N+1)%N||i==zz)
            continue;
        ans+=dp[(1<<N)-1][i];
    }
    return ans;
}

topcoder SRM 573 Div2 1000

00:00/00:00

1000:WolfPackDivTwo

题意:

你有一些点,每次你可以用一步的代价走到上下左右四个格子中的一个,然后问你走m步以后,所有点在同一个点上的种类数。。。

分析:

我们可以先dp出相对走到一个点的种类数,最后枚举终点就可以找到答案。。。

代码:

int num;
int dp[200][200][60];
int dx[]={0,1,-1,0,0};
int dy[]={0,0,0,-1,1};
int WolfPackDivTwo::calc(vector  x, vector  y, int m) 
{
    int ret=0;
    num=x.size();
    memset(dp,0,sizeof(dp));
    dp[55][55][0]=1;
    for(int i=1;i<=m;i++)
        for(int j=4;j<=106;j++)
            for(int k=4;k<=106;k++)
                for(int l=1;l<=4;l++)
                    dp[j][k][i]=(dp[j][k][i]+dp[j+dx[l]][k+dy[l]][i-1])%mod;
    for(int i=-m;i<=50+m;i++)
        for(int j=-m;j<=50+m;j++)
        {
            LL ans=1;
            for(int k=0;k<num;k++)
            {
                if(55-x[k]+i<0||55-y[k]+j<0){ans=0;break;}
                ans=ans*dp[55-x[k]+i][55-y[k]+j][m]%mod;
            }
            ret=(ret+ans)%mod;
        }
    return ret;
}

topcoder SRM 572 Div1 250+500

00:00/00:00

250:NewArenaPassword

题意:

给你一串字符串,你要把前k个字符和后k个字符转换成一样的,问你最少要几步。

分析:

因为长度小于50所以如果k小于len/2,我们直接暴力做就好了,如果大于一半我们发现相隔len-k的长度字符是一样的,我们直接找最多的就好了。。。

代码:

int len,ans;
int num[30];
int NewArenaPassword::minChange(string oldPassword, int K) 
{
    ans=0;
    len=oldPassword.size();
    if(K<len/2)
    {
        for(int i=0;i<K;i++)
            if(oldPassword[i]!=oldPassword[len-K+i])
                ans++;
    }
    else 
    {
        int flag=len-K;
        for(int i=0;i<flag;i++)
        {
            memset(num,0,sizeof(num));
            int maxn=0,tot=0;
            for(int j=0;j*flag+i<len;j++)
            {
                tot++;
                num[oldPassword[i+j*flag]-'a']++;
                maxn=max(maxn,num[oldPassword[i+j*flag]-'a']);
            }
            ans+=tot-maxn;
        }
    }
    return ans;
}

500:EllysBulls

题意:

某人有一个长度小于9的密码,你连续猜小于50次,每次他都会告诉你你猜对了几位,然后,问你密码是多少,有多个就输出”Ambiguity”,没有答案输出”Liar”。。。

分析:

这个题目我请教了周发发大佬,大佬一看是tc的题目,就给出了一个暴力加优化,然后说tc一秒十个亿,然后我打完T掉了。。。是这样的长度是9时,我们枚举前5位,然后剩下的询问中找对最多的,然后枚举哪几位对,最后验证就好了,理论可以过然后我太菜了,打了一个晚上没过。。。

代码:

int num,siz,ret;
int ans[10];
vector q;
vector r;
vector mdzz[5];
int anss[55];
int last[55];
inline void dfs_small(int now)
{
    if(ret>=2)return;
    if(now==num)
    {
        for(register int i=0;i<siz;++i)
        {
            int good=0;
            for(register int j=0;j<num;++j)
                if(q[i][j]-'0'==ans[j])
                    good++;
            if(good!=r[i])
                return;
        }   
        ret++;
        for(register int i=0;i<num;++i)
            anss[i]=ans[i];
        return;
    }
    for(register int i=0;i=2)
        return;
    if(now==num)
    {
        for(register int i=0;i<siz;++i)
        {
            int good=0;
            for(int j=6;j<num;++j)
                if(q[i][j]-'0'==ans[j])
                    good++;
            if(good!=last[i])
                return;
        }
        ret++;
        for(register int i=0;i>1,now+1);
    }
    else 
        for(register int i=0;i>1,now+1);
}
inline void dfs(int now)
{
    if(ret>=2)
        return;
    if(now==6)
    {
        for(register int i=0;i<siz;++i)
        {
            int good=0;
            for(int j=0;jr[i])
                return;
            last[i]=r[i]-good;
        }
        int maxn=-1;
        for(register int i=0;ilast[maxn])
                maxn=i; 
        if(last[maxn]>num-6)return;
        for(register int i=0;i<mdzz[last[maxn]].size();++i)
            dfs_GG(maxn,mdzz[last[maxn]][i],6);
        return ;
    }
    for(register int i=0;i<=9;i++)
    {
        ans[now]=i;
        dfs(now+1);
    }
}
inline void init()
{
    for(register int i=0;i<=4;++i)
        mdzz[i].clear();
    for(int i=0;i<(1<<(num-6));++i)
        mdzz[__builtin_popcount(i)].push_back(i);
}
inline string EllysBulls::getNumber(vector  guesses, vector  bulls) 
{
    ret=0;q=guesses;r=bulls;
    num=guesses[0].size();
    siz=guesses.size();
    if(num>6)
        init();
    if(num<=6)dfs_small(0);
    else dfs(0);
    if(ret==1)
    {
        string zz;
        for(register int i=0;i1)
        return "Ambiguity";
    else return "Liar";
}

topcoder SRM 572 Div2 1000

00:00/00:00

1000:DistinctRemainders

题意:

给你两个数,N和M,要求你找到一个数的序列,所有数对M取模互不相同,然后所有数的和为N。。。输出所有可能数。。。

分析:

因为每一个余数只能取一次,那我们写一个背包,表示取i个数后,和为j的种类数,然后考虑贡献就是当前值乘上把多余的数(N-j)分给他们的种类。。。

代码:

LL A(LL n,int m)
{
    if (n<m) return 0;
    LL ans=1;
    for(int i=1;i<=m;i++)
     ans=ans*((n-i+1)%mod)%mod;
    return ans;
}
int dp[55][2550];
LL ans;
int DistinctRemainders::howMany(long long N, int M) 
{
    int maxn=0;
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=0;i<M;i++)
    {
        maxn+=i;
        for(int j=i+1;j;j--) 
            for(int k=i;k<=maxn;k++)
                (dp[j][k]+=dp[j-1][k-i]%mod)%=mod;
    }
    ans=1;
    for(int i=2;i<=M;i++)
        for(int j=0;j<=maxn;j++)
            if((j%M)==(N%M))
            {
                LL flag=(N-j)/M;
                (ans+=dp[i][j]*(A(flag+i-1,i-1)%mod*i%mod))%=mod;
            }
    return ans;
}

topcoder SRM 571 Div2 1000

00:00/00:00

1000:MagicMoleculeEasy

题意:

给你一个一般图,图中有n个点(n小于50),每个点都有权值,你要选出一个点的集合,满足集合中正好有k个元素,每一条边的两个端点至少有一个存在于集合中,问你最大权值。。。

分析:

因为点很少,然后边也不多,那么我们直接暴力枚举每一条边两边定点的状态就好了,复杂的玄学。。。

代码:

 

int n,cnt,ans,ret;
int num[55],cost[55];
int vis[55];
struct Edge{int u,v;}edge[2550];
bool cmp(const int &a,const int &b){return cost[a]>cost[b];}
int check(int now)
{
    for(int i=now;iK)return;
    if(K==k&&check(now)) {ans=max(ans,ret);return;}
    if(kcnt)
    {
        int flag=ret;
        for(int i=1;i<=n;i++)
        {
            if(!vis[num[i]])
                ret+=cost[num[i]],k++;
            if(k==K)
                break;
        }   
        if(k==K)ans=max(ans,ret);
        ret=flag;return;
    }
    while((vis[edge[now].u]||vis[edge[now].v])&&nowcnt){dfs(now,k,K);return;}
    vis[edge[now].u]=1,ret+=cost[edge[now].u];
    dfs(now+1,k+1,K);
    vis[edge[now].v]=1,ret+=cost[edge[now].v];
    dfs(now+1,k+2,K);
    vis[edge[now].u]=0,ret-=cost[edge[now].u];
    dfs(now+1,k+1,K);
    vis[edge[now].v]=0,ret-=cost[edge[now].v];
}
int MagicMoleculeEasy::maxMagicPower(vector  magicPower, vector  magicBond, int k) {
    cnt=0;
    memset(num,0,sizeof(num));
    memset(vis,0,sizeof(vis));
    n=magicPower.size();
    for(int i=0;i<n;i++)
        cost[i+1]=magicPower[i],num[i+1]=i+1;
    sort(num+1,num+n+1,cmp);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(magicBond[i][j]=='Y')
                edge[++cnt].u=i+1,edge[cnt].v=j+1;
    ans=-1;dfs(1,0,k);
    return ans;
}

topcoder SRM 736 Div2 1000

1000:MazeWithKeys

题意:

给出一个图,图中有几种符号:

  • “ . ”表示当前位置是空地。。。
  • “ # ”表示当前位置是墙。。。
  • “ * ”表示终点。
  • 小写字母是钥匙,每种钥匙只能打开对应的大写字母的门。
  • 大写字母是铁门,每种门最多只有一个。

对于一个地图,你想要知道有多少的空地可以到达出口,为了使游戏显得不那么简单,你想要知道到达出口至少开一扇门的的空地有多少个。

分析:

因为这个图最大只有50*50,所以我们可以直接爆搜,当你找到一个钥匙时,判断是否有匹配的门,当你找到门时,看看有没有钥匙,然后爆搜就好了。。。然后题目有毒,至少一个表示不用开门的不符合条件。。。

代码:

int n,m,tox,toy,ans,flag;
char Map[55][55];
int vis[55][55],to[55][55];
int men[30],key[30];
struct Men{int x,y;}M[30];
int dx[]={0,1,-1,0,0};
int dy[]={0,0,0,1,-1};
void dfs(int x,int y)
{
    if(vis[x][y]==1||Map[x][y]=='#')
        return;
    if(xn||y>m||y<=0)
        return;
    if(65<=Map[x][y]&&Map[x][y]<=90)
    {
        men[Map[x][y]-64]=1;
        if(key[Map[x][y]-64]==1)
        {
            vis[x][y]=1;flag=1;
            for(int i=1;i=97&&Map[x][y]<=122)
    {
        key[Map[x][y]-96]=1;
        if(men[Map[x][y]-96]==1)
        {
            flag=1;
            dfs(M[Map[x][y]-96].x,M[Map[x][y]-96].y);
        }
    }
    for(int i=1;i<=4;i++)
        dfs(x+dx[i],y+dy[i]);
}
void dfs_ans(int x,int y,int k)
{
    if(Map[x][y]!='.'||xn||y>m||y<=0||to[x][y]==1)
        return;
    if(k==1) ans++;
    to[x][y]=1;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             
    for(int i=1;i<=4;i++)
        dfs_ans(x+dx[i],y+dy[i],k);
}
void dfs_GG(int x,int y)
{
    if(vis[x][y]==1||(Map[x][y]!='.'&&Map[x][y]!='*'&&Map[x][y]<97))
        return;
    if(xn||y>m||y<=0)
        return;
    vis[x][y]=1;
    for(int i=1;i<=4;i++)
        dfs_GG(x+dx[i],y+dy[i]);
}
int MazeWithKeys::startingPoints(vector  a) {
	memset(Map,0,sizeof(Map));
	memset(to,0,sizeof(to));
	ans=0;
	n=a.size(),m=a[0].size();
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            Map[i+1][j+1]=a[i][j];
            if(65<=a[i][j]&&a[i][j]<=90)
                M[a[i][j]-64].x=i+1,M[a[i][j]-64].y=j+1;
            if(a[i][j]=='*')
                tox=i+1,toy=j+1;
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(!to[i][j]&&Map[i][j]=='.')
            {
                memset(vis,0,sizeof(vis));
                memset(men,0,sizeof(men));
                memset(key, 0,sizeof(key));
                dfs_GG(i,j);
                if(vis[tox][toy]==1)
                    dfs_ans(i,j,0);
                else
                {
                    memset(vis,0,sizeof(vis));
                    flag=0;dfs(i,j);
                    if(vis[tox][toy]==1&&flag==1)
                        dfs_ans(i,j,1);
                    else dfs_ans(i,j,0);
                }
            }
    return ans;
}

Topcoder SRM 570 Div2 1000

1000:CentaurCompany

哎,好久没写Topcoder了,然后现在来补作业。。。

题意:

给你一棵树,询问其中有多少种连通块(可以不包含任何元素)。。。

分析:

大力搞一搞树形dp就好了,我们考虑dp[i]表示以i为根的子树中包含根的连通块数量。。。

代码:

 

LL way[55][55],n;
LL dp[55],ans;
void find(int now,int fa)
{
	vectorflag;
	flag.clear();
	for(int i=1;i<=n;i++)
		if(way[now][i]&&i!=fa)
		{
			find(i,now);
			flag.push_back(dp[i]);
		}
	if(flag.size()==0)
		dp[now]=1;
	else
	{
		dp[now]=flag[0]+1;
		for(int i=1;i<flag.size();i++)
			dp[now]*=flag[i]+1;
	}
	ans+=dp[now];
}
long long CentaurCompanyDiv2::count(vector  a, vector  b)
{
	ans=0;
	n=a.size()+1;
	memset(dp,0,sizeof(dp));
    memset(way,0,sizeof(way));
    for(int i=0;i<n-1;i++)
    	way[a[i]][b[i]]=way[b[i]][a[i]]=1;
    find(1,0);
    return ans+1;
}

topcoder SRM 568 Div1 250+500(失踪)

250:BallsSeparating

题意:

给你很多盒子,盒子里有红黄蓝三种球,然后,你可以把一个球从一个盒子移动到另一个盒子里去,问你最少移动几次。。。

分析:

由于盒子不多,我们直接枚举三个终点盒子给三种颜色,其余的直接贪心就好了。。。

代码:

int ans,siz;
int BallsSeparating::minOperations(vector  red, vector  green, vector  blue) {
    siz=red.size();ans=inf;
	if(siz<3)return -1;
	for(int i=0;i<siz;i++)
		for(int j=0;j<siz;j++)
			for(int k=0;k<siz;k++)
			{
				int sum=0;
				if(i==j||j==k||k==i)
					continue;
				for(int l=0;l<siz;l++)
				{
					if(l==i)
						sum+=green[l]+blue[l];
					else if(l==j)
						sum+=red[l]+blue[l];
					else if(l==k)
						sum+=red[l]+green[l];
					else 
						sum+=red[l]+green[l]+blue[l]-max(red[l],max(green[l],blue[l]));
				}
				ans=min(sum,ans);
			}
	return ans;
}