首页 > 代码库 > 每日总结-05-17
每日总结-05-17
今天真是极度的不爽,非常不爽!。
今天下午加了一场训练赛。没想到加题加难了。
。
。
加完题晚上一直在写JSP的作业,怎么也写不完,怎么也写不出来。。。
晚上回到宿舍也一直再调,结果最后调好了。提交作业的时候发现提交时间截止了,怎么能这么悲伤。
------------------------------------------------------------------------------------------------------------------------------------------------------------
言归正传:
下午做了一场周赛。
我做了俩题。
1,zoj-3761-Easy billiards
枚举随意两个点,假设两个点能够互相打击,就把这两个点连起来。
最后暴力DFS寻找图中有几个联通块。
#include<stdio.h> #include<algorithm> #include<iostream> #include<stdlib.h> #include<string.h> #include<vector> using namespace std; #define maxn 2200 struct list { int x; int y; friend bool operator <(const list &a,const list &b) { if(a.x!=b.x)return a.x<b.x; else return a.y<b.y; } } node[maxn]; vector<list>vec[maxn]; struct listt { int x; int y; int f; }; vector<listt>ans; int maps[maxn][maxn]; int l; int vis[maxn]; int n; void dfs(int x,int pre) { if(vis[x])return; vis[x]=1; for(int i=1;i<=n;i++) { if(maps[x][i]!=-1&&!vis[i]) { dfs(i,x); } } if(pre==-1)return; struct listt p; p.x=node[x].x; p.y=node[x].y; if(p.x==node[pre].x) { if(p.y>node[pre].y)p.f=1; else p.f=2; } if(p.y==node[pre].y) { if(p.x>node[pre].x) { p.f=4; } else p.f=3; } ans.push_back(p); } int main() { int i,j,k; while(~scanf("%d",&n)) { if(n==0) { cout<<"0"<<endl; continue; } memset(maps,-1,sizeof(maps)); memset(vis,0,sizeof(vis)); for(i=1; i<=n; i++) { scanf("%d%d",&node[i].x,&node[i].y); vec[i].clear(); } sort(node+1,node+n+1); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(node[i].x==node[j].x||node[i].y==node[j].y)maps[i][j]=1; } } ans.clear(); int nums; nums=0; for(i=1;i<=n;i++) { if(vis[i])continue; dfs(i,-1); nums++; } cout<<nums<<endl; for(i=0;i<ans.size();i++) { struct listt p; p=ans[i]; if(p.f==1)printf("(%d, %d) DOWN\n",p.x,p.y); else if(p.f==2)printf("(%d, %d) UP\n",p.x,p.y); else if(p.f==3)printf("(%d, %d) RIGHT\n",p.x,p.y); else printf("(%d, %d) LEFT\n",p.x,p.y); } } return 0; }
2,zoj-3765-Lights
伸展树的模板题,没想到由于写搓了一个i。就TLE了10次。。
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<vector> using namespace std; #define maxn 350000 #define mem(a,b) memset(a,b,sizeof(a)) #define root10 ch[ch[root][1]][0] #define root1 ch[root][1] int pre[maxn],ch[maxn][2],root,tot; int size[maxn]; int key[maxn]; int st[maxn]; int gcd1[maxn]; int gcd0[maxn]; int n; int pos; struct list { int val; int st; } node[maxn]; int gcd(int x,int y) { // return 1; if(x<y)swap(x,y); if(y==0)return x; return gcd(y,x%y); } void init() { root=tot=0; ch[root][0] = ch[root][1] = size[root] = pre[root] = 0; gcd0[root] = gcd1[root] = 0; } void newnode(int &x,int k,int father) { x=++tot; pre[x]=father; size[x]=1; ch[x][0]=ch[x][1]=0; key[x]=node[k].val; st[x]=node[k].st; gcd0[x]=gcd1[x]=0; if(st[x]==0)gcd0[x]=node[k].val; else gcd1[x]=node[k].val; //cout<<gcd0[x]<<" "<<gcd1[x]<<endl; } void push_down(int x) { } void push_up(int x) { int ll=ch[x][0]; int rr=ch[x][1]; size[x]=size[ll]+size[rr]+1; gcd0[x]=gcd(gcd0[ll],gcd0[rr]); gcd1[x]=gcd(gcd1[ll],gcd1[rr]); if(st[x])gcd1[x]=gcd(gcd1[x],key[x]); else gcd0[x]=gcd(gcd0[x],key[x]); } void rot(int x,int kind) { int y=pre[x]; push_down(y); push_down(x); ch[y][!kind]=ch[x][kind]; pre[ch[x][kind]]=y; if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x; pre[x]=pre[y]; ch[x][kind]=y; pre[y]=x; push_up(y); push_up(x); } void splay(int x,int goal) { push_down(x); while(pre[x]!=goal) { if(pre[pre[x]]==goal) { push_down(pre[x]); push_down(x); rot(x,ch[pre[x]][0]==x); } else { int y=pre[x]; push_down(pre[y]); push_down(y); push_down(x); int kind=ch[pre[y]][0]==y; if(ch[y][kind]==x) { rot(x,!kind); rot(x,kind); } else { rot(y,kind); rot(x,kind); } } } push_up(x); if(goal==0)root=x; } void buildtree(int &x,int l,int r,int father) { if(l>r)return ; int mid=(l+r)/2; newnode(x,mid,father); buildtree(ch[x][0],l,mid-1,x); buildtree(ch[x][1],mid+1,r,x); push_up(x); } int get_kth(int x,int k) { push_down(x); int p=size[ch[x][0]]; if(p+1==k)return x; else if(k<=p)return get_kth(ch[x][0],k); else get_kth(ch[x][1],k-p-1); } int que(int l,int r,int st) { int x=get_kth(root,l); splay(x,0); int y=get_kth(root,r+2); splay(y,root); int ans; if(st==0)ans=gcd0[root10]; else ans=gcd1[root10]; if(ans==0)return -1; else return ans; } void add(int x,int val,int st) { int l=get_kth(root,x+1); splay(l,0); int r=get_kth(root,x+2); splay(r,root); n++; node[n].st=st; node[n].val=val; newnode(root10,n,root1); push_up(root1); push_up(root); } void del(int x) { int xx=get_kth(root,x); splay(xx,0); int y=get_kth(root,x+2); splay(y,root); pre[root10]=0; root10=0; push_up(root1); push_up(root); } void resst(int x) { int xx=get_kth(root,x); splay(xx,0); int y=get_kth(root,x+2); splay(y,root); st[root10]^=1; push_up(root10); push_up(root1); push_up(root); } void resval(int x,int vv) { int xx=get_kth(root,x); splay(xx,0); int y=get_kth(root,x+2); splay(y,root); key[root10]=vv; push_up(root10); push_up(root1); push_up(root); } char str[101]; int main() { int m,i,j,l,r,val,x; int stt; while(~scanf("%d%d",&n,&m)) { init(); node[0].st=0;node[0].val=0; for(i=1; i<=n; i++) { scanf("%d%d",&node[i].val,&node[i].st); } newnode(root,0,0); newnode(root1,0,root); buildtree(root10,1,n,root1); push_up(root1); push_up(root); int ii; for(ii=1; ii<=m; ii++) { // debug(); scanf("%s",str); if(str[0]==‘Q‘) { scanf("%d%d%d",&l,&r,&stt); printf("%d\n",que(l,r,stt)); } if(str[0]==‘I‘) { scanf("%d%d%d",&i,&val,&stt); add(i,val,stt); } if(str[0]==‘D‘) { scanf("%d",&i); del(i); } if(str[0]==‘R‘) { scanf("%d",&i); resst(i); } if(str[0]==‘M‘) { scanf("%d%d",&i,&x); resval(i,x); } } } return 0; }
---------------------------------------------------------------------
今天继续A了一个AC自己主动机的题目:
hdu-2296-Ring
须要记录路径,比較麻烦。
用string记录比較方便。
#include<stdio.h> #include<algorithm> #include<iostream> #include<stdlib.h> #include<string.h> #include<string> using namespace std; const int maxnode=110*11; const int childnum=26; const int mod=20090717; string path[55][maxnode]; struct ac_tree { int chd[maxnode][childnum]; int val[maxnode]; int fail[maxnode]; int Q[maxnode]; int ID[128]; int sz; int dp[55][maxnode]; void init() { fail[0]=0; for(int i=0; i<childnum; i++) { ID[i+‘a‘]=i; } } void reset() { memset(chd,0,sizeof(chd)); sz=1; } void insert(char str[],int k) { int p=0; int len=strlen(str); for(int i=0; i<len; i++) { int c=ID[str[i]]; if(!chd[p][c]) { memset(chd[sz],0,sizeof(chd[sz])); val[sz]=0; chd[p][c]=sz++; } p=chd[p][c]; } val[p]=k; // cout<<str<<" "<<p<<endl; } void ac_build() { int *s=Q,*e=Q; for(int i=0; i<childnum; i++) { if(chd[0][i]) { fail[chd[0][i]]=0; *e++=chd[0][i]; } } while(s!=e) { int u=*s++; for(int i=0; i<childnum; i++) { int &v=chd[u][i]; if(v) { *e++=v; fail[v]=chd[fail[u]][i]; // val[v]=(val[v]+val[fail[v]]); } else v=chd[fail[u]][i]; } } } void work(int n) { int ans=0; memset(dp,-1,sizeof(dp)); dp[0][0]=0; for(int i=0; i<=n; i++) for(int j=0; j<sz; j++) path[i][j].clear(); for(int i=0; i<n; i++) { for(int j=0; j<sz; j++) { if(dp[i][j]==-1) continue; for(int k=0; k<26; k++) { int cur=chd[j][k]; if(dp[i][j]+val[cur]>dp[i+1][cur]) { dp[i+1][cur]=dp[i][j]+val[cur]; path[i+1][cur]=path[i][j]+(char)(k+‘a‘); } else if(dp[i][j]+val[cur]==dp[i+1][cur]&&path[i][j]+(char)(k+‘a‘)<path[i+1][cur]) { path[i+1][cur]=path[i][j]+(char)(k+‘a‘); } } } } for(int i=1; i<=n; i++) for(int j=0; j<sz; j++) ans=max(ans,dp[i][j]); if(ans==0) { puts(""); return; } // cout<<ans<<endl; string str=" "; for(int i=1; i<=n; i++) for(int j=0; j<sz; j++) if(dp[i][j]==ans&&(str==" "||(path[i][j].size()<str.size()||(path[i][j].size()==str.size()&&path[i][j]<str)))) str=path[i][j]; cout<<str<<endl; } } AC; char temp[110][15]; int main() { AC.init(); int n,m,k; int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); AC.reset(); for(int i=1; i<=m; i++) { scanf("%s",temp[i]); } for(int i=1; i<=m; i++) { scanf("%d",&k); AC.insert(temp[i],k); } //cout<<")"<<endl; AC.ac_build(); AC.work(n); } return 0; }
每日总结-05-17
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。