T1
傻逼题……不想写贴昨年代码了。
总之随便怎么搞都能过、
15年的DAY2T1怎么那么毒瘤真是越活越倒退】
#include <iostream> #include <fstream> #include <cstdlib> #include <cstring> #include <cmath> using namespace std; ifstream fin("wireless.in"); ofstream fout("wireless.out"); struct lk { int x; int y; int gs; }; lk citys[22]; int fw=0,lks=0; int search(int xc,int yc);//查找当前范围有多少个公共设施被覆盖 int main(void) { fin>>fw>>lks; int a=0,b=0,sl=0; for(int i=1;i<=lks;i++) { fin>>a>>b>>sl; citys[i].x=a; citys[i].y=b; citys[i].gs=sl; } int ans=0,tot=0,fas=0; for(int i=0;i<=128;i++) { for(int j=0;j<=128;j++) { tot=search(i,j); if(ans==tot)fas++; if(ans<tot)fas=1; ans=max(tot,ans); } } fout<<fas<<" "<<ans; return 0; } int search(int xc,int yc) { int pdx=0,pdy=0,zgs=0; for(int i=1;i<=lks;i++) { pdx=abs(citys[i].x-xc); pdy=abs(citys[i].y-yc); if(pdx<=fw&&pdy<=fw)zgs+=citys[i].gs; } return zgs; }
T2
先反边，求一遍终点能到的点。再预处理一下判定那些点可以出现在路径上、
最后随便搜一下。
这题最后一个数据专卡DFS。卡得飞起，换成了BFS之后快得飞起、】
#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> using namespace std; struct lb { int nw; int to; }; lb line[200003],anti[200003]; int n=0,m=0,head[10003]={0},anth[10003]={0}; int cnt1=0,cnt2=0,st=0,ed=0,dis[10003]={0}; int check[10003]={0}; void add(int f,int t); void a_add(int f,int t); void fid(int nw); void solve(); int main(void) { freopen("road.in","r",stdin); freopen("road.out","w",stdout); memset(dis,0x7f/2,sizeof(dis)); const int INF=dis[0]; scanf("%d%d",&n,&m); int a=0,b=0; for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); add(a,b); a_add(b,a); } scanf("%d%d",&st,&ed); check[ed]=1; fid(ed); int next=0; for(int i=1;i<=n;i++) { if(check[i]) { for(int j=head[i];j>0;j=line[j].to) { next=line[j].nw; if(check[next]==0) { check[i]=-1; break; } } } } dis[st]=0; solve(); if(dis[ed]!=INF)printf("%d",dis[ed]); else printf("-1 "); return 0; } void add(int f,int t) { line[++cnt1].nw=t; line[cnt1].to=head[f]; head[f]=cnt1; return; } void a_add(int f,int t) { anti[++cnt2].nw=t; anti[cnt2].to=anth[f]; anth[f]=cnt2; return; } void fid(int nw) { if(nw>n)return; int next=0; for(int i=anth[nw];i>0;i=anti[i].to) { next=anti[i].nw; if(check[next])continue; check[next]=1; fid(next); } return; } void solve() { int dl[30003]={0},tou=0,wei=1,next=0; dl[1]=st; do { tou++; if(tou>30000)tou=1; for(int i=head[dl[tou]];i>0;i=line[i].to) { next=line[i].nw; if(dis[next]<=dis[dl[tou]]+1||check[next]!=1)continue; wei++; if(wei>30000)wei=1; dl[wei]=next; dis[next]=dis[dl[tou]]+1; } }while(tou!=wei); return; }
T3
我不会搞啊真的不会搞啊
但是我A过QAQ昨年AC过这题QAQ
代码贴上来好了……
#include <algorithm> #include <iostream> #include <fstream> #include <cstdlib> #include <cstring> #include <string> #include <cmath> using namespace std; ifstream fin("equation.in"); ofstream fout("equation.out"); long long int xs[110][6]={0};//系数 const int mo[6]={0,10007,11261,14843,19997,21893}; long long int pd[22000][5]={0}; int N=0,M=0,ans[1001001]={0},gs=0; void dr(int bh); long long int ycl(int sum,int mox);//传说中的预处理 int main(void) { fin>>N>>M; for(int i=1;i<=N+1;i++)dr(i); // for(int i=1;i<=N+1;i++)cout<<xs[i][1]<<" "; for(int i=1;i<=5;i++) { for(int j=1;j<=mo[i];j++) { pd[j][i]=ycl(j,i); } } bool fg=false; for(int i=1;i<=M;i++) { fg=false; for(int j=1;j<=5;j++) { if(pd[i%mo[j]][j]) { fg=true; break; } } if(fg==false)ans[++gs]=i; } fout<<gs<<" "; for(int i=1;i<=gs;i++)fout<<ans[i]<<" "; return 0; } void dr(int bh) { string s; bool jl=false; fin>>s; for(int i=0;i<s.size();i++) { if(s[i]=='-')jl=true; else { for(int j=1;j<=5;j++) { xs[bh][j]=(xs[bh][j]*10+s[i]-'0')%mo[j]; } } } if(jl) for(int i=1;i<=5;i++)xs[bh][i]=mo[i]-xs[bh][i]; } long long int ycl(int sum,int mox) { long long int tot=0ll; for(int i=N+1;i>0;i--) { tot=(tot*sum+xs[i][mox])%mo[mox]; //if(sum==1)cout<<tot<<" "; } return tot; }