總結：全是模擬…以及讀入處理體驗好差hhh
一套卷子（4/4AK）
T3
題目大意：給出一棵樹，從0節點開始走m步，求可訪問的最多節點數（一個節點訪問多次僅算一次）
n , m < = 1000 n,m<=1000 n,m<=1000
真有你的網易…省選原題都拿來出啊…（不過我做過hhh
直接放原題鏈接了： C Q O I 2017 CQOI2017 CQOI2017 小Q的棋盤
簡要題解：
策略是：先考慮直接直接按最長鏈走，如果走完最長鏈有多的步數，可以在一開始先走支鏈，貢獻按2步/一個節點算，
故有以下代碼：
for(int i=0;i<=n;i++) mx=Math.max(mx,dep[i]);
if(m<=mx-1) System.out.println(m+1);
else System.out.println(Math.min(n,mx+(m-mx+1)/2));
然后dfs算一波就行了，
import java.io.*;
import java.util.*;
public class zbr01
{
public static int []x=new int [100005];
static List []g=new List[100005];
public static int []dep=new int [100005];
public static int []used=new int [100005];
public static int n,m;
public static void dfs(int u)
{
used[u]=1;
for(int i=0;i<g[u].size();i++)
{
int v=(int)g[u].get(i); if(used[v]==1) continue;
dep[v]=dep[u]+1; dfs(v);
}
}
public static void main(String[] args)
{
Scanner S=new Scanner(System.in);
int n=S.nextInt(),m=S.nextInt(); n--;
for(int i=0;i<=n;i++) g[i]=new ArrayList <Integer>();
for(int i=1;i<=n;i++)
{
int u=S.nextInt(),v=i;
g[u].add(v); g[v].add(u);
}
dep[0]=1; dfs(0); int mx=0;
for(int i=0;i<=n;i++) mx=Math.max(mx,dep[i]);
if(m<=mx-1) System.out.println(m+1);
else System.out.println(Math.min(n,mx+(m-mx+1)/2));
}
}
T2
題目大意：給出字串s，求一個最長的連續子串使得其中的 a , b , c , x , y , z a,b,c,x,y,z a,b,c,x,y,z出現次數均為偶數，(復雜度要求 O ( n ) O(n) O(n))
它又又又又來了！hash又是你！！！
將abcdef的出現次數%2，進行hash處理，就能用一個數字表示一個狀態了，
（日常學好hash筆試必過）
import java.io.*;
import java.util.*;
public class zbr01
{
public static int []x=new int [100005];
public static void main(String[] args)
{
Scanner S=new Scanner(System.in);
String s=S.nextLine(); int l=s.length();
int a=0,b=0,c=0,d=0,e=0,f=0,ans=0;
for(int i=0;i<=64;i++) x[i]=-1; x[0]=0;
for(int i=0;i<l;i++)
{
char p=s.charAt(i);
if(p=='a') a++; else if(p=='b') b++;
else if(p=='c') c++; else if(p=='x') d++;
else if(p=='y') e++; else if(p=='z') f++;
a%=2; b%=2; c%=2; d%=2; e%=2; f%=2;
int nw=32*a+16*b+8*c+4*d+2*e+f;
int tmp=x[nw];
if(tmp==-1) x[nw]=i;
else if(nw==0) ans=Math.max(ans,i-tmp+1);
else ans=Math.max(ans,i-tmp);
}
System.out.println(ans);
}
}
T4
題目大意：裸二分圖匹配…略略略（連題面都懶得改了嗎hhh，直接男女配對了hhh）
下面是網路流大板子+惡心的讀入處理emm…
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
inline int read()
{
int x=0,w=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
return w==1?x:-x;
}
struct node{int from,to,cap,flow;};
vector <node> edges;
vector <int> mp[maxn];
int n,m,s,t,d[maxn],cur[maxn];
bool vis[maxn];
queue <int> que;
inline void add_edge(int u,int v,int w)
{
edges.push_back((node){u,v,w,0});
edges.push_back((node){v,u,0,0});
int pp=edges.size();
mp[u].push_back(pp-2);
mp[v].push_back(pp-1);
}
inline bool bfs()
{
for(int i=0;i<=t;i++) d[i]=inf,vis[i]=0; d[s]=0; vis[s]=1; que.push(s);
while(!que.empty())
{
int u=que.front(); que.pop();
for(int i=0;i<mp[u].size();i++)
{
node v=edges[mp[u][i]];
if(v.cap-v.flow>0&&!vis[v.to])
{
d[v.to]=d[u]+1;
vis[v.to]=1; que.push(v.to);
}
}
}
if(vis[t]) return true;
return false;
}
inline int dfs(int u,int w)
{
int flow=0,r=0;
if(u==t||w==0) return w;
for(int i=0;i<mp[u].size();i++)
{
node &v=edges[mp[u][i]];
if(d[v.to]==d[u]+1&&(r=dfs(v.to,min(v.cap-v.flow,w)))>0)
{
flow+=r;
edges[mp[u][i]].flow+=r;
edges[mp[u][i]^1].flow-=r;
w-=r;
if(w==0) break;
}
}
return flow;
}
inline int max_flow()
{
int ff=0;
while(bfs())
{
memset(cur,0,sizeof(cur));
ff+=dfs(s,inf);
}
return ff;
}
int a[maxn],b[maxn],ca,cb;
map <int,int> pa,pb;
int main()
{
freopen("t1.in","r",stdin);
string S=""; getline(cin,S);
int l=S.length(),nw=0;
for(int i=0;i<l;i++)
{
if(S[i]==' ')
{
a[++ca]=nw;
pa[nw]=ca;
nw=0;
}
else nw=nw*10+S[i]-'0';
}
a[++ca]=nw; pa[nw]=ca;
nw=0; getline(cin,S);
for(int i=0;i<l;i++)
{
if(S[i]==' ')
{
b[++cb]=nw;
pb[nw]=cb;
nw=0;
}
else nw=nw*10+S[i]-'0';
}
b[++cb]=nw; pb[nw]=cb; nw=0;
S=ca+cb+1; t=ca+cb+2;
rep(i,1,ca) add_edge(s,i,1);
rep(i,1,cb) add_edge(ca+i,t,1);
int Q=read();
while(Q--)
{
int u=read(),v=read();
add_edge(pa[u],ca+pb[v],1);
}
printf("%d\n",max_flow());
return 0;
}
T1
題目大意：給出一顆二叉樹，問兩個兒子都是葉節點的節點數量，
毫無水平的大模擬…略略略…扔到最后hhh
import java.io.*;
import java.util.*;
public class zbr01
{
public static int []x=new int [100005];
static List []g=new List[100005];
public static int []dep=new int [100005];
public static int []cnt=new int [100005];
public static int n,m;
public static void dfs(int u,int fa)
{
if(g[u].size()==1&&u!=1)
{
for(int i=0;i<g[u].size();i++)
{
int v=(int)g[u].get(i);
cnt[v]++;
}
}
for(int i=0;i<g[u].size();i++)
{
int v=(int)g[u].get(i); if(v==fa) continue;
dep[v]=dep[u]+1; dfs(v,u);
}
}
public static void main(String[] args)
{
Scanner S=new Scanner(System.in);
int n=S.nextInt(),m=S.nextInt();
for(int i=0;i<=n;i++) g[i]=new ArrayList <Integer>();
for(int i=1;i<=m;i++)
{
int u=S.nextInt();
String tmp=S.next(); int v=S.nextInt();
g[u].add(v); g[v].add(u);
}
dep[0]=1; dfs(1,0); int ans=0;
for(int i=1;i<=n;i++) if(cnt[i]==2) ans++;
System.out.println(ans);
}
}
另一套C++題的T4：
題目大意：求兩個字串的編輯距離，有的字串可以無視，
讀入非常惡心…然后編輯距離就是大家都會的非常經典的dp了…詳見代碼
巨長碼農題
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
inline int read()
{
int x=0,w=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
return w==1?x:-x;
}
map <string,int> p;
string a[maxn],b[maxn];
int dp[1005][1005],ca,cb;
int main()
{
string s; getline(cin,s); int l=s.length();
string tmp="";
for(int i=0;i<l;i++)
{
if(s[i]==' ')
{
p[tmp]=1;
tmp="";
}
else tmp+=s[i];
}
p[tmp]=1; tmp="";
getline(cin,s); l=s.length();
for(int i=0;i<l;i++)
{
if(s[i]==' ')
{
a[++ca]=tmp;
tmp="";
}
else tmp+=s[i];
}
a[++ca]=tmp; tmp="";
getline(cin,s); l=s.length();
for(int i=0;i<l;i++)
{
if(s[i]==' ')
{
b[++cb]=tmp;
tmp="";
}
else tmp+=s[i];
}
b[++cb]=tmp; tmp="";
rep(i,0,ca) rep(j,0,cb) dp[i][j]=inf; dp[0][0]=0;
rep(i,1,ca) dp[i][0]=dp[i-1][0]+(p[a[i]]==0);
rep(i,1,cb) dp[0][i]=dp[0][i-1]+(p[b[i]]==0);
rep(i,1,ca) rep(j,1,cb)
{
if(p[a[i]]) dp[i][j]=min(dp[i][j],dp[i-1][j]);
else dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
if(p[b[j]]) dp[i][j]=min(dp[i][j],dp[i][j-1]);
else dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
if(p[a[i]]&&p[b[j]]) dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
else dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
if(a[i]==b[j]) dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
}
cout<<dp[ca][cb]<<endl;
return 0;
}
END：網易讀入太惡心了…碼量也好大emm…以及這hash是不是已經連著出10多場了hhh…公司之間大家這么有默契？？？
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/34620.html
標籤：其他