【TYVJ水题三连发】1502 兴建高铁 1568 Rabbit Number 1673 位图-白红宇

【TYVJ水题三连发】1502 兴建高铁 1568 Rabbit Number 1673 位图

阅读量：4328 次

发布时间：2019-06-06

本文共 2893 字，大约阅读时间需要 9 分钟。

说是水题。。其实本蒟蒻1A的也只有第二道。。。惭愧惭愧。。。

TYVJ1502 兴建高铁

这个题目其实就是一搜索，愿意BFS或者DFS都可以，SPFA也随意。不过鉴于数据不大，推荐还是DFS（写起来比较短嘛）

Code:

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;int n,ans=99999999,tot=99999999;int g[51][51],v[51],w[51],p[51];void dfs(int now,int max1,int max2,int cost,int pass){	p[pass]=now;	if (now==1){		int pp;		switch (pass){			case 1:pp=cost;break;			case 2:pp=cost-max1;break;			default:pp=cost-max1-max2;break;		}		if ((pp
          
           
            =max1) dfs(i,g[now][i],max1,cost+g[now][i],pass+1); else if (g[now][i]>=max2) dfs(i,max1,g[now][i],cost+g[now][i],pass+1); else dfs(i,max1,max2,cost+g[now][i],pass+1); v[i]--; }}int main(){ cin >>n; for (int i=1;i<=n;i++){ int a,b,c; cin >>a >>b >>c; g[a][b]=g[b][a]=c; } v[0]++; dfs(0,0,0,0,0); cout <<0; for (int i=1;i<=tot;i++) cout <<" " <

TYVJ1568 Rabbit Number

这个题目第一反应是打表，第二反应还是打表。

不过后来发现在程序里算也不会超，关键是搜的时候要注意一点：组成Rabbit Number的数位不可能达到4（证明很简单。。不行题解里也有），然后就随便搜搜就可以了。

Code:

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #define sqr(a) a*ausing namespace std;const long limit=1000000001;int all=0;long long num[100001];long long calc(long long x){ int now=0; while (x){ now+=x%10; x=x/10; } return now;}int check(long long x){ if (calc(sqr(x))==sqr(calc(x))) return 1; else return 0;}void dfs(long long now){ //cout <
             
              <
              
               limit) return; if (check(now)) { all++; num[all]=now; } if (now) dfs(now*10); dfs(now*10+1); dfs(now*10+2); dfs(now*10+3);}int main(){ long long l,r; memset(num,0,sizeof(num)); cin >>l >>r; dfs(0); all+=10; sort(num,num+all); int b=1,e=all; while (!num[b]) b++; while (!num[e]) e--; while (num[b]
               
                r) e--; cout <
                
                 <

TYVJ1673 位图

这题目一开始还困扰了我很久。。

打开题解，一句”用广搜可过“让我压力巨大。。

后来发现，原来不是对每个点搜最近的白点，而是从白点开始floodfill。。这样就可以秒杀了。。

我还是太弱了。。。

Code:

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #define sqr(a) a*ausing namespace std;const int dx[5]={0,1,-1,0,0};const int dy[5]={0,0,0,1,-1};int l,r,n,m;int v[201][201],s[100001][2];int main(){ char c; scanf("%d %d\n",&n,&m); l=1;r=0; for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++){ scanf("%c",&c); while ((c!='0')&&(c!='1')) scanf("%c",&c); if (c=='0') v[i][j]=0; else{ r++;s[r][1]=i;s[r][2]=j; v[i][j]=1; } } } while (l<=r){ for (int i=1;i<=4;i++){ int nowx=s[l][1]+dx[i],nowy=s[l][2]+dy[i]; if ((nowx)&&(nowy)&&(nowx<=n)&&(nowy<=m)&&(!v[nowx][nowy])){ v[nowx][nowy]=v[s[l][1]][s[l][2]]+1; r++;s[r][1]=nowx;s[r][2]=nowy; } } l++; } for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++){ if (j!=1) cout <<" "; cout <

转载于:https://www.cnblogs.com/JS-Shining/archive/2012/06/11/2545633.html

你可能感兴趣的文章