HDU_Steps9.1 雜題 HDU2054 HDU1789 HDU2159 HDU1401 HDU2818 HDU3465 HDU2433 HDU3524

HDU2054 A == B ?

坑爹題，題意說的太不清楚了。注意幾點，前面的0，有小數點時後面的0，以及正負數(不同号時僅有0相等)

#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
int main(){
	string s1,s2;
	while(cin>>s1>>s2){
		int l1=s1.size()-1;//後面
		int l2=s2.size()-1;
		int r1=0,r2=0;//前面
		//記錄符号是否相同符号
		bool ff=true;
		if((s1[0]=='-'&&s2[0]!='-')||(s2[0]=='-'&&s1[0]!='-')){
			ff=false;
		}
		//如果有小數點去後面的0
		if(s1.find('.')!=string::npos){
			while(l1>=0){
				if(s1[l1]>='1'&&s1[l1]<='9')break;
				if(s1[l1]=='.'){l1--;break;}
				l1--;
			}
		}
		if(s2.find('.')!=string::npos){
			while(l2>=0){
				if(s2[l2]>='1'&&s2[l2]<='9')break;
				if(s2[l2]=='.'){l2--;break;}
				l2--;	
			}
		}		
		//去前面的0；
		while(r1<l1){
			if((s1[r1]>='1'&&s1[r1]<='9')||s1[r1]=='.')break;
			r1++;
		}
		while(r2<l2){
			if((s2[r2]>='1'&&s2[r2]<='9')||s2[r2]=='.')break;
			r2++;
		}
		//剩下的長度
		if(r2-l2!=r1-l1){
			printf("NO\n");
			continue;
		}
		if(ff==false&&s2[r2]=='0'){
			printf("YES\n");
			continue;	
		}
		//比較
		bool flag=true;
		for(int i=r2,j=r1;i<=l2&&j<=l1;i++,j++){
			if(s1[j]!=s2[i])flag=false;	
		}
		printf(flag&&ff?"YES\n":"NO\n");
	}
	return 0;
}

HDU1789 Doing Homework again

一道簡單談心，分值大的先安排，并且盡量靠後，不能安排的就減去該分值

HDU2159 FATE

有一定的精力值，和殺怪上限，更新需要一定的經驗值，問最大能保留多少忍耐度,DP

#include<cstdio>
#include<string.h>
using namespace std;
int n,m,k,s,a[101],b[101];
/*一邊扯淡一邊亂寫就A了。。
 * 就是一個無窮物品的背包，d[i]表示這一點可達到的最大經驗，d2[i]表示達到這一經驗最少要殺多少隻怪
 * 優先DP經驗，經驗相同時使隻數最少
 * 最後從頭掃描一遍，找出經驗足夠且隻數在範圍内的最小耗費精力值
 */
int main(){
	while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF){
		for(int i=1;i<=k;i++)scanf("%d%d",&a[i],&b[i]);
		//DP
		int d[105],d2[105];
		memset(d,-1,sizeof d);
		memset(d2,-1,sizeof d2);
		d[0]=d2[0]=0;
		for(int i=1;i<=k;i++){
			for(int j=b[i];j<=m;j++){
				if(d[j-b[i]]!=-1&&d[j-b[i]]+a[i]>d[j]){
					d[j]=d[j-b[i]]+a[i];
					d2[j]=d2[j-b[i]]+1;
				}
				if(d[j-b[i]]!=-1&&d[j-b[i]]+a[i]==d[j]&&d2[j]>d2[j-b[i]]+1){
					d2[j]=d2[j-b[i]]+1;	
				}
			}	
		}
		
		bool flag=false;
		for(int i=1;i<=m;i++){
			if(d[i]>=n&&d2[i]<=s){
				printf("%d\n",m-i);
				flag=true;
				break;	
			}
		}
		if(!flag)printf("-1\n");
		
	}
	return 0;	
}

HDU1401 Solitaire

每次可移動一步或跳過一步，給定初始态和終态，問是否在八步内可達。我的第一道雙向廣搜，每個方向隻搜4層，如果目前的狀态已經在另一個方向中通路過了就說明在8步内可達，标記通路用的是char類型，這樣才能保證不超記憶體。

#include<cstdio>
#include<queue>
#include<algorithm>
#include<string.h>
using namespace std;
struct node{
	int r,c;	
	bool operator <(const node& n)const{
		return r<n.r||(r==n.r&&c<n.c);	
		
	}
};
struct state{
	node nd[4];
	int step;
}sta,end;
int st[8],en[8];
int dr[]={1,0,-1,0},dc[]={0,1,0,-1};
char vis[8][8][8][8][8][8][8][8];//0代表未通路，1代表正向，2代表反向(short(正好32M)和int都會超)
void visit(state s,char v){
	sort(s.nd,s.nd+4);
	vis[s.nd[0].r][s.nd[0].c][s.nd[1].r][s.nd[1].c][s.nd[2].r][s.nd[2].c][s.nd[3].r][s.nd[3].c]=v;
}
char gvisit(state s){
	sort(s.nd,s.nd+4);
	return vis[s.nd[0].r][s.nd[0].c][s.nd[1].r][s.nd[1].c][s.nd[2].r][s.nd[2].c][s.nd[3].r][s.nd[3].c];
}
bool inbfs(queue<state> &q,short now,short opp){
	state ost=q.front();q.pop();
	if(ost.step>4)return false;//每個隊列隻搜四步
	
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			state nst=ost;
			int nr=nst.nd[i].r+dr[j];
			int nc=nst.nd[i].c+dc[j];
			bool jump2=false,canmv=true;
			for(int k=0;k<4;k++){//如果有點已經在這個位置了，就再向這個方向走一步
				if(i==k)continue;
				if(ost.nd[k].r==nr&&ost.nd[k].c==nc){
					nr+=dr[j],nc+=dc[j];
					jump2=true;
					break;	
				}	
			}
			if(jump2){//如果走了兩步步就要再判，如果還重合就不可走了
				for(int k=0;k<4;k++){
					if(i==k)continue;
					if(ost.nd[k].r==nr&&ost.nd[k].c==nc){
						canmv=false;
						break;	
					}	
				}	
			}
			if(canmv&&nr>=0&&nc>=0&&nr<=7&&nc<=7){
				nst.nd[i].r=nr,nst.nd[i].c=nc,nst.step=ost.step+1;
				char v=gvisit(nst);	
				if(v==now)continue;//如果這個點被目前隊列通路果
				else if(v==opp)return true;//如果這個點被另一隊列通路過，說明再八步内可以走到
				else if(v==0){
					visit(nst,now);
					q.push(nst);	
				}
			}
		}	
	}
	return false;
}
bool bfs(){
	memset(vis,0,sizeof vis);
	queue<state> q1,q2;
	q1.push(sta);
	visit(sta,1);
	q2.push(end);
	visit(end,2);
	
	while(!q1.empty()||!q2.empty()){
		if(!q1.empty()){if(inbfs(q1,1,2))return true;};	
		if(!q2.empty()){if(inbfs(q2,2,1))return true;};
	}
	return false;
}
int main(){
	while(scanf("%d",&st[0])!=EOF){
		for(int i=1;i<8;i++)scanf("%d",&st[i]);	
		for(int i=0;i<8;i++)scanf("%d",&en[i]);	
		for(int i=0;i<4;i++){
			sta.step=end.step=1;
			sta.nd[i].r=st[i*2]-1;
			sta.nd[i].c=st[i*2+1]-1;
			end.nd[i].r=en[i*2]-1;	
			end.nd[i].c=en[i*2+1]-1;	
		}
		printf(bfs()?"YES\n":"NO\n");
	}
	return 0;	
}

HDU2818 Building Block

簡單并查集，加入表示這一堆的方塊個數以及某一塊方塊下面有多少個方塊的數組

#include<cstdio>
using namespace std;
const int maxn=30003;
int p[maxn],u[maxn],t[maxn];
void init(){
	//父節點，這堆的元素數，某節點下面的方塊數
	for(int i=0;i<maxn;i++){
		p[i]=i,t[i]=1,u[i]=0;
	}
}
int find(int x){
	if(x!=p[x]){
		int tmp=find(p[x]);
		u[x]+=u[p[x]];
		p[x]=tmp;
	}
	return p[x];
}
void merge(int x,int y){
	int fx=find(x);
	int fy=find(y);
	if(fx==fy)return;
	p[fx]=fy;
	u[fx]=t[fy];
	t[fy]+=t[fx];
}


int n,a,b;
char op[3];
int main(){
	while(scanf("%d",&n)!=EOF){
		init();
		while(n--){
			scanf("%s",op);
			if(op[0]=='M'){
				scanf("%d%d",&a,&b);
				merge(a,b);	
			}else{
				scanf("%d",&a);
				find(a);
				printf("%d\n",u[a]);
			}
		}	
	}
	return 0;
}

HDU3465 Life is a Line

給出N條線段，求在(l,r)内有多少條線段相交,其實是求逆序對。。

#include<cstdio>
#include<algorithm>
using namespace std;
/*給出N條線段，求在(l,r)内有多少條線段相交，用li表示直線與l的交點，ri同理
 *對于l1<l2弱r2>r1則會相交，轉化未求逆序對，用歸并排序即可
 * 注意處理x2=x1(x1在(l,r)内會與所有非豎直直線相交)的情況以及l1=l2的情況(l相等時按r排序)
 * */
struct point{
	double l,r;	
	bool operator<(const point& p)const{
		return l<p.l(l==p.l&&r<p.r);	
	}
}p[50005];
double ll,rr,x1,y1,x2,y2,ar[50005],tar[50005];
int n,ps,sz,rs;
void merge(int l,int m,int r){
	int l1=l,l2=m+1,pp=0;
	while(l1<=m&&l2<=r){
		if(ar[l1]<=ar[l2]){
			tar[pp++]=ar[l1++];	
		}else{
			tar[pp++]=ar[l2++];
			rs+=m-l1+1;
		}
	}
	while(l1<=m)tar[pp++]=ar[l1++];
	while(l2<=r)tar[pp++]=ar[l2++];
	for(int i=l,j=0;i<=r;i++,j++){
		ar[i]=tar[j];	
	}
}
void mergesort(int l,int r){
	if(l>=r)return;
	int m=(l+r)/2;
	mergesort(l,m);
	mergesort(m+1,r);
	merge(l,m,r);
}

int main(){
	 while(scanf("%d",&n)!=EOF){
		scanf("%lf%lf",&ll,&rr); 
		sz=0,ps=0;
		for(int i=0;i<n;i++){
			scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
			if(x2==x1){
				if(ll<x1&&x1<rr)sz++;	
			}else{
				p[ps].l=y1+(y2-y1)*(ll-x1)/(x2-x1);
				p[ps].r=y1+(y2-y1)*(rr-x1)/(x2-x1);
				ps++;
			}
		}
		sort(p,p+ps);
		for(int i=0;i<ps;i++)ar[i]=p[i].r;
		
		rs=0;
		mergesort(0,ps-1);
		rs+=sz*ps;
		printf("%d\n",rs);
	}
	
	return 0;	
}

HDU2433 Travel

問減去每一條路後剩餘的每兩點間的最短路和。做法比較暴力，先對每一個點BFS，求出每個點到其它所有點的最短路和，并标記”最短路樹“中的邊。然後删邊時如果該邊在該點生成的最短路樹中，就重新BFS，若不在，就直接取記錄的值。

#include<cstdio>
#include<string.h>
#include<queue>
using namespace std;
int n,m;
struct edge{
	short u,v,n,i;
}ed[6002];
short first[105],vis[105];
int sl[105];
bool flag,hash[105][3005];
void adde(short u,short v,short ind){
	ed[ind].u=u,ed[ind].v=v,ed[ind].i=ind%m;
	ed[ind].n=first[u];
	first[u]=ind;
}
void bfs(short st,int bj){//傳入起點和要去的邊,bj=-1時代表是初始化
	memset(vis,0,sizeof vis);
	vis[st]=1;
	queue<short> q;
	q.push(st);
	
	while(!q.empty()){
		int t=q.front();q.pop();
		for(int i=first[t];i!=-1;i=ed[i].n){
			int v=ed[i].v;
			if(vis[v]||ed[i].i==bj)continue;
			vis[v]=vis[t]+1;
			if(bj==-1){
				hash[st][ed[i].i]=1;//标記“最短路生成樹”
			}
			q.push(v);
		}	
	}
}
int main(){
	while(scanf("%d%d",&n,&m)!=EOF){
		memset(first,-1,sizeof first);
		memset(hash,0,sizeof hash);
		memset(sl,0,sizeof sl);
		flag=true;//标記是否連通
		
		short tu,tv;
		for(int i=0;i<m;i++){//鄰接表存圖
			scanf("%hd%hd",&tu,&tv);	
			adde(tu,tv,i);
			adde(tv,tu,m+i);
		}
		bool fir=true;
		for(int i=1;i<=n&&flag;i++){//預處理，求出每個點到其它點集的最短路和
			bfs(i,-1);
			if(fir){//判斷是否連通，注意隻要進行一次
				for(int j=1;j<=n;j++)if(!vis[j])flag=false;
				fir=false;	
			}	
			for(int j=1;j<=n;j++){
				sl[i]+=vis[j]-1;
			}
		}
		for(int i=0;i<m;i++){
			if(flag==false){//圖不連通，去邊必然不連通
				printf("INF\n");
				continue;
			}
			int res=0;
			for(int j=1;j<=n&&flag;j++){
				if(hash[j][i]==0){//如果該點的最短路樹不包含i邊，去了也沒有影響
					res+=sl[j];
				}else{//否則重新bfs,注意去掉第i邊
					bfs(j,i);
					for(int k=1;k<=n;k++)if(!vis[k])flag=false;//看是否連通
					if(flag){
						for(int k=1;k<=n;k++){
							res+=vis[k]-1;
						}		
					}
				}
			}	
			if(flag==false){//去邊後導緻不連通
				printf("INF\n");
				flag=true;
			}else{
				printf("%d\n",res);	
			}
		}
 
		
	}
	return 0; 	
}

HDU3524 Perfect Squares

i^2 mod 2^n (i<n)會有多少個不同的結果，數學真是做不來，還好能打表找到規律

#include<cstdio>
#include<vector>
#include<string.h>
using namespace std;
/* 打表找出規律 
 * F(n)=2^(2n-1)-5(2^(2n-2)-1)/3 奇數時
 * F(n)=2^(2n-1)-4(2^(2n-2)-1)/3 偶數時
 */
/* 求(4^(n-1)-1)/3 mod 10007
 * 4^(n-1)-1(mod 10007*3)的結果/3
 * 也可4^(n-1)-1(mod 10007)*inv(3)
 * inv(3) 3x=1 mod 10007
 */
typedef long long LL;
const LL MOD=10007;
int cas;
LL n;
LL pmod(LL p,LL k,LL mod){
	if(k==0)return 1;
	if(k==1)return p;
	LL r=pmod(p,k/2,mod);
	r=(r*r)%mod;
	if(k&1)r=(r*p)%mod;
	return r;
}
int main(){
	scanf("%d",&cas);
	for(int ca=1;ca<=cas;ca++){
		scanf("%lld",&n);
		LL base=(n&1)?5:4;
		n=(n+1)/2;
		LL r=(pmod(4,n-1,MOD)*2)%MOD;
		LL r2=(pmod(4,n-1,MOD*3)+MOD*3-1)%(MOD*3)/3;
		r=(r+MOD-(base*r2)%MOD)%MOD;
		printf("Case #%d: %lld\n",ca,r);
	}
	return 0;	
}

HDU_Steps9.1 雜題 HDU2054 HDU1789 HDU2159 HDU1401 HDU2818 HDU3465 HDU2433 HDU3524

繼續閱讀

probe()函數是什麼時候被調用，裝置和驅動是怎麼聯系起來的

invalid byte 1 of 1-byte UTF-8 sequence

二叉樹先序、中序、後序三種周遊的非遞歸算法

轉詳解C#資料庫存取圖檔三大方式

C/C++頭檔案、函數使用說明

java 日期總結

設定某一行背景顔色的CListCtrl

BMP檔案結構及圖像每行位元組計算方法

linux網絡程式設計----發送與接收檔案

處理PCX檔案

C#多線程——前台線程和背景線程

QName是什麼

Android – ListView 中添加按鈕，動态删除添加ItemView的操作

Git學習筆記5 merge沖突時二選一

GridView終極用法(一)

Linux裝置模型（中）之上層容器