Update：3/11日停更，刷PAT的题目去了(: 。
2019/3/1
CF 1130D1 Toy Train (Simplified)
先把每个点处理，计算该点运送完需要的时间；遍历每个点时给它绕一圈，找到时间最长的那个，那个就是把所有运送完所需的时间。注意如果没有货物，需要跳过该点。
1 #include <vector> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 8 const int N=222; 9 const int INF=0x3f3f3f3f; 10 int ans[N]; 11 vector <int> s[N]; 12 13 int main(){ 14 int n,m; 15 scanf("%d%d",&n,&m); 16 for(int i=1;i<=m;i++){ 17 int a,b; 18 scanf("%d%d",&a,&b); 19 s[a].push_back(b); 20 } 21 for(int i=1;i<=n;i++){ 22 int mi=INF; 23 for(int j=0;j<s[i].size();j++){ 24 int u=s[i][j]; 25 if(u>=i) mi=min(mi,u-i); 26 else mi=min(mi,n-i+u); 27 } 28 if(mi!=INF) ans[i]=n*(s[i].size()-1)+mi; 29 } 30 for(int i=1;i<=n;i++){ 31 int res=0,time=n,k=i,cnt=0; 32 while(time--){ 33 //注意 34 if(ans[k]!=0) res=max(res,ans[k]+cnt); 35 k++; 36 if(k==n+1) k=1; 37 cnt++; 38 } 39 printf("%d ",res); 40 } 41 return 0; 42 }
2019/3/2
CF 1130D2 Toy Train
和上题一样，改下long long就可以了，发现自己一开始写的就挺优的，O(n^2)。
1 #include <vector> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 8 const int N=5555; 9 typedef long long ll; 10 ll ans[N]; 11 vector <int> s[N]; 12 13 int main(){ 14 int n,m; 15 scanf("%d%d",&n,&m); 16 for(int i=1;i<=m;i++){ 17 int a,b; 18 scanf("%d%d",&a,&b); 19 s[a].push_back(b); 20 } 21 for(int i=1;i<=n;i++){ 22 ll mi=1e18; 23 for(int j=0;j<s[i].size();j++){ 24 int u=s[i][j]; 25 if(u>=i) mi=min(mi,1LL*(u-i)); 26 else mi=min(mi,1LL*(n-i+u)); 27 } 28 if(mi!=1e18) ans[i]=1LL*n*(s[i].size()-1)+mi; 29 } 30 for(int i=1;i<=n;i++){ 31 ll res=0; 32 int time=n,k=i,cnt=0; 33 while(time--){ 34 if(ans[k]!=0) res=max(res,ans[k]+cnt); 35 k++; 36 if(k==n+1) k=1; 37 cnt++; 38 } 39 printf("%lld ",res); 40 } 41 return 0; 42 }
2019/3/3
CF 1114C Trailing Loves (or L'oeufs?)
b分解质因子，每个质因子对n!求指数，要使b全部符合，那么最少的那个指数就为答案。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 typedef long long ll; 8 ll n,b,ans=1e18; 9 10 void cal(ll num,ll cnt){ 11 ll tmp=1,res=0; 12 while(tmp<=n/num){ 13 tmp*=num; 14 res+=n/tmp; 15 } 16 ans=min(ans,res/cnt); 17 } 18 19 int main(){ 20 scanf("%lld%lld",&n,&b); 21 for(ll i=2;i*i<=b;i++){ 22 if(b%i==0){ 23 ll cnt=0; 24 while(b%i==0){ 25 b/=i; 26 cnt++; 27 } 28 cal(i,cnt); 29 } 30 } 31 if(b>1) cal(b,1); 32 printf("%lld\n",ans); 33 return 0; 34 }
2019/3/4
CF 1114D Flood Fill（区间DP）
$dp[l][r][0]$表示以c[l]为整块颜色的最小花费，$dp[l][r][1]$表示以c[r]为整块颜色的最小花费。
转移方程：
$dp[l][r][0]=min(dp[l+1][r][0]+(c[l]!=c[l+1]),dp[l+1][r][1]+(c[l]!=c[r]))$
$dp[l][r][1]=min(dp[l][r-1][0]+(c[l]!=c[r]),dp[l][r-1][1]+(c[r-1]!=c[r]))$
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 const int N=5555; 8 int c[N],dp[N][N][2]; 9 10 int main(){ 11 memset(dp,0x3f,sizeof(dp)); 12 int n; 13 scanf("%d",&n); 14 for(int i=1;i<=n;i++){ 15 scanf("%d",&c[i]); 16 dp[i][i][0]=dp[i][i][1]=0; 17 } 18 for(int len=2;len<=n;len++){ 19 for(int l=1;l<=n;l++){ 20 int r=l+len-1; 21 if(r>n) break; 22 dp[l][r][0]=min(dp[l+1][r][0]+(c[l]!=c[l+1]),dp[l+1][r][1]+(c[l]!=c[r])); 23 dp[l][r][1]=min(dp[l][r-1][0]+(c[l]!=c[r]),dp[l][r-1][1]+(c[r-1]!=c[r])); 24 } 25 } 26 printf("%d\n",min(dp[1][n][0],dp[1][n][1])); 27 return 0; 28 }
2019/3/5
CF 1111C Creative Snap
DFS二分区间，比较继续二分后的代价和当前代价大小。区间长度问题可以二分区间。整体就是二分套二分啦。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 const int N = 1e5 + 10; 8 int n, k, A, B; 9 int a[N]; 10 typedef long long ll; 11 12 ll dfs(int l, int r){ 13 int len = upper_bound(a + 1, a + 1 + k, r) - upper_bound(a + 1, a + 1 + k, l - 1 ); 14 ll res = 0; 15 if(len) { 16 res = 1LL * B * len * (r - l + 1); 17 } else { 18 return A; 19 } 20 if(l == r) return res; 21 int mid = (l + r) / 2; 22 res = min(res, dfs(l, mid) + dfs(mid + 1, r)); 23 return res; 24 } 25 26 int main() { 27 scanf("%d %d %d %d", &n, &k, &A, &B); 28 for(int i = 1; i <= k; i++) { 29 scanf("%d", &a[i]); 30 } 31 sort(a + 1, a + 1 + k); 32 printf("%lld\n", dfs(1, (1<<n) )); 33 return 0; 34 }
2019/3/6
CF 1111B Average Superhero Gang Power
排序后，从后往前累加，在当前数之前的数都删掉，剩下来的m给当前和之后的数平均分下去，如果平均分下去大于k，那就只给k，否则就可以全部分下去，更新下答案。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 typedef long long ll; 8 const int N = 1e5 + 10; 9 ll a[N]; 10 11 int main() { 12 double ans = 0; 13 int n, k, m; 14 scanf("%d %d %d", &n, &k, &m); 15 for(int i = 1; i <= n; i++) { 16 scanf("%lld", &a[i]); 17 } 18 sort(a + 1, a + 1 + n); 19 ll sum = 0; 20 for(int i = n; i >= 1; i--) { 21 sum += a[i]; 22 if(m >= i - 1 ) { 23 int new_m = m - i + 1; 24 int ave = new_m / (n - i + 1); 25 if(ave >= k) { 26 ans = max(ans, 1.0 * sum / (n - i + 1) + 1.0 * k); 27 } else { 28 ans = max(ans, (1.0 * sum + 1.0 * new_m) / (n - i + 1) ); 29 } 30 } 31 } 32 printf("%.10f", ans); 33 return 0; 34 }
2019/3/7
CF 1132 Painting the Fence
先枚举下第一个人画的区间，处理完后把第二个人画的区间用前缀处理下。最后遍历下所有人，更新答案。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 const int N = 5555; 8 int p[N], l[N], r[N], cnt[N]; 9 10 int main() { 11 int n, q, ans = 0, res = 0; 12 scanf("%d %d", &n, &q); 13 for(int i = 1; i <= q; i++) { 14 scanf("%d %d", &l[i], &r[i]); 15 for(int j = l[i]; j <= r[i]; j++) { 16 p[j]++; 17 if(p[j] == 1) ans++; 18 } 19 } 20 for(int i = 1; i <= q; i++) { 21 int sum = ans; 22 for(int k = l[i]; k <= r[i]; k++) { 23 p[k]--; 24 if(p[k] == 0) sum--; 25 } 26 for(int k = 1; k <= n; k++) { 27 if(p[k] == 1) cnt[k] = 1; 28 else cnt[k] = 0; 29 cnt[k] += cnt[k-1]; 30 } 31 for(int k = i + 1; k <= q; k++) { 32 res = max(res, sum - (cnt[ r[k] ] - cnt[ l[k] - 1 ])); 33 } 34 for(int k = l[i]; k <= r[i]; k++) { 35 p[k]++; 36 } 37 } 38 printf("%d", res); 39 return 0; 40 }
2019/3/8
CF 1107D Compression
先暴力枚举出原来的n x n矩阵，然后对能整除n的数字进行判断，每一块负责的是否符合要求。更新最大的答案。（矩阵压缩）
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 const int N = 6666; 8 typedef long long ll; 9 int n, ans = 0; 10 string str, s[N]; 11 12 string cal(char ch) { 13 if(ch == '0') return "0000"; 14 if(ch == '1') return "0001"; 15 if(ch == '2') return "0010"; 16 if(ch == '3') return "0011"; 17 if(ch == '4') return "0100"; 18 if(ch == '5') return "0101"; 19 if(ch == '6') return "0110"; 20 if(ch == '7') return "0111"; 21 if(ch == '8') return "1000"; 22 if(ch == '9') return "1001"; 23 if(ch == 'A') return "1010"; 24 if(ch == 'B') return "1011"; 25 if(ch == 'C') return "1100"; 26 if(ch == 'D') return "1101"; 27 if(ch == 'E') return "1110"; 28 if(ch == 'F') return "1111"; 29 } 30 31 bool check(int k) { 32 for(int x = 0; x < n; x+=k) { 33 for(int y = 0; y < n; y+=k) { 34 char ch = s[x][y]; 35 for(int i = x; i < x + k; i++) { 36 for(int j = y; j < y + k; j++) { 37 if(s[i][j] != ch) return false; 38 } 39 } 40 } 41 } 42 return true; 43 } 44 45 int main() { 46 ios::sync_with_stdio(false); 47 cin >> n; 48 for(int i = 0; i < n; i++) { 49 cin >> str; 50 for(int j = 0; j < str.size(); j++) { 51 s[i] = s[i] + cal(str[j]); 52 } 53 } 54 for(int i = 1; i <= n; i++) { 55 if(n % i == 0) { 56 if(check(i)) ans = i; 57 } 58 } 59 cout << ans << endl; 60 return 0; 61 }
2019/3/9
CF 1133F1 Spanning Tree with Maximum Degree
从度数最大的点BFS一下即可。
1 #include <queue> 2 #include <vector> 3 #include <cstdio> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 8 const int N = 2e5 + 10; 9 int n, m; 10 int d[N]; 11 bool vis[N]; 12 vector<int> E[N]; 13 14 void bfs(int st) { 15 queue<int> Q; 16 Q.push(st); 17 vis[st] = 1; 18 while(!Q.empty()) { 19 int u = Q.front(); 20 Q.pop(); 21 for(int i = 0; i < E[u].size(); i++) { 22 int v = E[u][i]; 23 if(!vis[v]) { 24 printf("%d %d\n", u, v); 25 vis[v] = 1; 26 Q.push(v); 27 } 28 } 29 } 30 } 31 32 int main() { 33 scanf("%d %d", &n, &m); 34 for(int i = 1; i <= m; i++) { 35 int u, v; 36 scanf("%d %d", &u, &v); 37 E[u].push_back(v); 38 E[v].push_back(u); 39 d[u]++;d[v]++; 40 } 41 int mx = 0, id = 0; 42 for(int i = 1; i <= n; i++) { 43 if(d[i] > mx) { 44 mx = d[i]; 45 id = i; 46 } 47 } 48 bfs(id); 49 return 0; 50 }
2019/3/10
CF 1137A Skyscrapers
离散化。
1 #include <queue> 2 #include <vector> 3 #include <cstdio> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 8 const int N = 1234; 9 int a[N][N]; 10 vector<int> r[N],c[N]; 11 12 int main() { 13 int n, m; 14 scanf("%d %d", &n, &m); 15 for(int i = 0; i < n; i++) { 16 for(int j = 0; j < m; j++) { 17 scanf("%d", &a[i][j]); 18 r[i].push_back(a[i][j]); 19 c[j].push_back(a[i][j]); 20 } 21 } 22 for(int i = 0; i < n; i++) { 23 sort(r[i].begin(), r[i].end()); 24 r[i].erase(unique(r[i].begin(), r[i].end()), r[i].end()); 25 } 26 for(int i = 0; i < m; i++) { 27 sort(c[i].begin(), c[i].end()); 28 c[i].erase(unique(c[i].begin(), c[i].end()), c[i].end()); 29 } 30 for(int i = 0; i < n; i++) { 31 for(int j = 0; j < m; j++) { 32 int p1 = lower_bound(r[i].begin(), r[i].end(), a[i][j]) - r[i].begin(); 33 int p2 = lower_bound(c[j].begin(), c[j].end(), a[i][j]) - c[j].begin(); 34 int p3 = r[i].end() - lower_bound(r[i].begin(), r[i].end(), a[i][j]); 35 int p4 = c[j].end() - lower_bound(c[j].begin(), c[j].end(), a[i][j]); 36 printf("%d", max(p1, p2) + max(p3, p4)); 37 if(j == m - 1) printf("\n"); 38 else printf(" "); 39 } 40 } 41 return 0; 42 }