nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

第一题

输入一个n,表示n个点的完全图,输入m表示后续有m个操作,输入s表示你站在s点这个位置
接下来m行,每行两个数字x,y
如果x=0 表示与y相连的所有边断开
否则 表示边x-y断开
你需要输出一个数x,表示这m个操作的前x个操作可以让s点与其他所有点断开连接

1
2
3
4
5
6
7
8
9
10
11
12
13
set<int>se;
for(int i=1;i<=m;i++){
cin>>x>>y;
if(x==0) {
if(y==s) return i;
else se.insert(y);
}else {
if(x==s) se.inesrt(y);
if(y==s) se.insert(x);
}
if(se.size()==n) return i;
}
return 0;

怎么说呢,我就是这样写的,显然se.size()==n写错了,应该说n-1,跟yg讲这题的时候才想起来,我原地爆炸了,一直怀疑题目有问题,然后只过了10%,到最后都没找到bug

第二题

输入一个数n表示n个人,输入一个数m表示他们搞了m次聚会,输入一个数f表示f被感染了
他们举办聚会,如果聚会中有一个人被感染,则参加聚会的其他人都会被感染
输入m行,每行行首一个q,表示这一次聚会有q个人参加,q后面跟着q个数,表示这q个人的编号
你需要输出最终多少人被感染了

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i=0;i<m;i++){
cin>>q;
vector<int> vec;
for(int i=0;i<q;i++) {
cin>>x;
vec.push_back(x);
if(dead[x]) flag=true;
}
if(flag) for(int x:vec) dead[x]=true;
}
int ans=0;
for(bool x:dead) if(x) ans++;
cout<<ans<<endl;

这代码能有问题??????只能过60%,开玩笑呢

第三题

给一个数字字符串S,一个数字m,
你需要计算出S有多少个划分,讲他划分为S1,S2,S3,。。 且每个数都是m的倍数,答案对1e9+7取模

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
static String s;
static BigInteger split(int l,int r){
return new BigInteger(s.substring(l,r+1));
}

static int mod=(int)(1e9+7);
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
int T= cin.nextInt();
for(int ii=0;ii<T;ii++) {
int n=cin.nextInt();
BigInteger m=cin.nextBigInteger();
s = cin.next();
long dp[]= new long[n+100];
for(int i=0;i<n;i++){
dp[i]=m.mod(split(0,i)).equals(BigInteger.ZERO)?1:0;
for(int j=1;j<=i;j++){
if(split(j,i).mod(m).equals(BigInteger.ZERO)) dp[i]=(dp[i]+dp[j-1])%mod;
}
}
System.out.println(dp[n-1]);
}
}


}

java代码在这,我库鸟。这代码TLE,后来跟yg讲的时候发现split(i,j)%mod这句话可以通过字符串hash优化到O1,我真是,为什么笔试的时候没想到呢

第四题

太菜了,没看

叙述题

50G的文件,每行一个int,你需要在512MB内存的机器上求出TOP100
这个很有意思,显然mapreduce
先说一个常规的做法,抽象为n个int,取出TOP m
我们每次从n个数中选出k个来,求这k个数的TOP m,使用线性时间选择算法
这里一共执行了$$\lceil \frac{n}{k}\rceil$$次,取出了不超过$$\lceil \frac{n}{k}\rceilm$$个数,于是合并解的时候复杂度为$$O(\lceil \frac{n}{k}\rceilm)$$, 前面的复杂度为$$O(n)$$, 所以总时间复杂度为$$O(n+\lceil \frac{mn}{k}\rceil)$$

空间复杂度的话就是$$O(k)+O(\lceil \frac{mn}{k}\rceil)$$

我们稍微权衡一下,很容易发现时间复杂度就是$$O(n)$$,空间复杂度当k取到$$\sqrt{mn}$$的时候达到最优为$$O(\sqrt{mn})$$

然后我们来讲mapreduce的做法,我们每份分出去x台机器,map时间复杂度为$$O(n)$$,其他机器上为$$O(\frac{n}{x})$$,然后reduce,我们还有$$xm$$个数,总共是$$O(n+\frac{n}{x}+xm)$$