居然不让切本地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; }
全部评论
(20) 回帖