8.23 字节笔试
居然不让切本地IDE，后面有时间补下代码
1. 数组和模3为0的个数
DP，dp[i][j]表示i个数，和模3为j的方案数。AC
#include <bits/stdc++.h>
using namespace std;
int n, l, r;
long long dp[500005][3];
int main()
{
int mod = 1000000007;
scanf("%d %d %d", &n, &l, &r);
dp[0][0] = 1LL;
for(int i = 1 ; i <= n ; i++){
int a[3];
for(int j = 0 ; j < 3 ; j++){
int p = r/3 + (r%3>=j);
int q = (l-1)/3 + ((l-1)%3>=j);
a[j] = p - q;
}
dp[i][0] = dp[i-1][0]*a[0] + dp[i-1][1]*a[2] + dp[i-1][2]*a[1];
dp[i][1] = dp[i-1][0]*a[1] + dp[i-1][1]*a[0] + dp[i-1][2]*a[2];
dp[i][2] = dp[i-1][0]*a[2] + dp[i-1][1]*a[1] + dp[i-1][2]*a[0];
for(int j = 0 ; j < 3 ; j++)
dp[i][j] %= mod;
}
printf("%lld\n", dp[n][0]);
return 0;
}
2.
dfs骗分，20%
骗分代码就不写了😂
3.
暴力骗分，30%
4. 问建图后是否为联通且无环。
n<10000暴力，n>10000不会，直接输出NO，居然过了...
#include <bits/stdc++.h>
using namespace std;
bool f(int a, int b, int c, int d){
if(a<=c && b>=d)
return false;
if(c<=a && d>=b)
return false;
if(b<c || a>d)
return false;
return true;
}
int main()
{
int T, n;
scanf("%d", &T);
while(T--){
scanf("%d", &n);
vector<int> p(n, 0);
vector<int> q(n, 0);
for(int i = 0 ; i < n ; i++)
scanf("%d %d", &p[i], &q[i]);
if(n > 10000){ //不加能过60%，会超时。
// 堵出题人样例是机器随机生成，大概率不满足。
printf("NO\n");
continue;
}
vector<int> g[n];
int sum = 0; //统计边数
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < i ; j++){
if(f(p[i], q[i], p[j], q[j])){
g[i].push_back(j); //建无向图
g[j].push_back(i);
sum++;
}
}
}
vector<bool> vis(n, 0);
queue<int> que;
que.push(0);
vis[0] = true;
while(!que.empty()){
int t = que.front();
que.pop();
for(int i = 0; i < g[t].size(); i++){
if(vis[g[t][i]]) continue;
vis[g[t][i]] = true;
que.push(g[t][i]);
}
}
bool flag = true; //判断是否连通
for(int i = 0 ; i < n ; i++)
if(vis[i] == false)
flag = false;
if(sum == n-1 && flag)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
