A. 赤
我本来想考虑一下当a=n或b=n的情况，就以另一个变量作为关键字排序，如果a=n就选喜欢吃豆干可能性大的前b个两种食物全给，后面的只给干脆面，结果还交了个0分……
鉴于这道题的正解既涉及期望，又需要什么wqs二分还套两层，还是来日方长吧……
Cat只有被捕捉的份还不够去捕捉别的猫……
B. Tourist Attractions
TLE 40：4层循环枚举经过的4个点分别是什么，O(n^4).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1507;
const ll mod = 1e9 + 7;
int n, ans;
char s[maxn];
vector<int> son[maxn];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
int main()
{
n = read();
for(int i=1; i<=n; i++)
{
scanf("%s", s+1);
for(int j=1; j<=n; j++)
{
if(s[j] == '1') son[i].push_back(j);
}
}
for(int i=1; i<=n; i++)
{
int sz1 = son[i].size();
for(int j=0; j<sz1; j++)
{
int u = son[i][j]; if(u == i) continue;
int sz2 = son[u].size();
for(int k=0; k<sz2; k++)
{
int v = son[u][k]; int sz3 = son[v].size();
if(v == i || v == u) continue;
for(int d=0; d<sz3; d++)
{
if(son[v][d] == i || son[v][d] == u || son[v][d] == v) continue;
//printf("path: %d %d %d %d\n", i, u, v, son[v][d]);
ans++;
}
}
}
}
printf("%d\n", ans);
return 0;
}
View Code
TLE 70：循环一层起点，然后进入dfs枚举中间的两个点并把已选的点做上标记，直接加上最后一个点可以通向的点让它们当终点，再循环一下已经选的点里面如果有的点出现在第3个点通向的点集里答案-1.
所以相当于优化了最后一层循环，O(n^3).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1507;
int mp[maxn][maxn], n, sum[maxn], b[5];
ll ans = 0;
bool vis[maxn];
char s[maxn];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
void dfs(int u, int dep)
{
b[dep] = u;
if(dep == 3)
{
ans += sum[u];
for(int i=1; i<=3; i++) if(mp[u][b[i]]) ans--;
return;
}
for(int i=1; i<=n; i++)
{
if(mp[u][i] && !vis[i])
{
vis[i] = 1;
dfs(i, dep+1);
vis[i] = 0;
}
}
}
int main()
{
n = read();
for(int i=1; i<=n; i++)
{
scanf("%s", s+1);
for(int j=1; j<=n; j++)
{
if(s[j] == '1') mp[i][j] = 1;
}
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
sum[i] += mp[i][j];
}
}
for(int i=1; i<=n; i++)
{
vis[i] = 1;
dfs(i, 1);
vis[i] = 0;
}
printf("%lld\n", ans);
return 0;
}
View Code
正解：其实连起点都不用枚举，只需要枚举中间的两个点，以它们俩为中心拓展找出起点和终点，要注意不能构成三元环(循环保证了二元环不会出现)，可以把枚举出来的中间的两个点的集合做一下&运算来去掉有环的两种情况，一种是从第二个点出发(和2号相连)能到终点(和3号相连)，另一种是从起点(和2号相连)出发能到第4个点(和三号相连)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1507;
const ll mod = 1e9 + 7;
int n;
ll ans;
char s[maxn];
bitset<maxn> b[maxn];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
int main()
{
n = read();
for(int i=1; i<=n; i++)
{
scanf("%s", s+1);
for(int j=1; j<=n; j++)
{
if(s[j] == '1') b[i][j] = 1;
}
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(b[i][j] == 0) continue;
int r1 = b[i].count()-1;
int r2 = b[j].count()-1;
int r3 = (b[i]&b[j]).count();
ans += r1 * r2 - r3;
}
}
printf("%lld\n", ans);
return 0;
}
View Code
标签：ch,int,ll,long,maxn,邀请赛,getchar From： https://www.cnblogs.com/Catherine2006/p/16596551.html