A.拼英语水平和手速的签到题
1 #include2 3 using namespace std; 4 5 int s, v1, v2, t1, t2; 6 7 int main() { 8 cin >> s >> v1 >> v2 >> t1 >> t2; 9 int a1 = t1 + v1 * s + t1;10 int a2 = t2 + v2 * s + t2;11 if(a1 < a2) puts("First");12 else if(a1 > a2) puts("Second");13 else puts("Friendship");14 return 0;15 }
B.同签到
1 #include2 3 using namespace std; 4 5 int k, n, a[10]; 6 7 string s; 8 9 long long sum;10 11 int main() {12 cin >> k >> s;13 for(int i = 0;i < s.size();i ++)14 a[s[i] - '0'] ++, sum += s[i] - '0';15 if(sum >= k) {16 puts("0");17 return 0;18 }19 k -= sum;20 for(int i = 0;i < 10;i ++)21 for(int j = 1;j <= a[i];j ++) {22 k -= 9 - i, n ++;23 if(k <= 0) {24 printf("%d\n", n);25 return 0;26 }27 }28 return 0;29 }
C.看到xyc的数据范围就能明白是道水题...然后就WA了
1W个位置10W个点，可能一个位置好几颗星星...令人无语
1 #include2 3 using namespace std; 4 5 vector c[11][110][110]; 6 7 int n, q, cc, b[11][110][110]; 8 9 int main() {10 scanf("%d %d %d", &n, &q, &cc), cc ++;11 for(int u, v, w, i = 1;i <= n;i ++) {12 scanf("%d %d %d", &u, &v, &w);13 c[0][u][v].push_back(w);14 }15 for(int i = 1;i < cc;i ++)16 for(int j = 1;j <= 100;j ++)17 for(int k = 1;k <= 100;k ++)18 if(c[i - 1][j][k].size() != 0) {19 for(int p = 0;p < c[i - 1][j][k].size();p ++)20 c[i][j][k].push_back((c[i - 1][j][k][p] + 1) % cc);21 }22 for(int i = 0;i < cc;i ++)23 for(int j = 1;j <= 100;j ++)24 for(int k = 1;k <= 100;k ++) {25 b[i][j][k] += b[i][j - 1][k] + b[i][j][k - 1] - b[i][j - 1][k - 1];26 for(int p = 0;p < c[i][j][k].size();p ++)27 b[i][j][k] += c[i][j][k][p];28 }29 for(int t, A, B, C, D, i = 1;i <= q;i ++) {30 scanf("%d %d %d %d %d", &t, &A, &B, &C, &D);31 t %= cc, printf("%d\n", b[t][C][D] + b[t][A - 1][B - 1] - b[t][A - 1][D] - b[t][C][B - 1]);32 }33 return 0;34 }
如果没有亮度变化，坐标到1e9，会有新的星星在某个位置出现，询问不变
允许离线的话可以CDQ分治解决，O(nlog^2n)
强制在线的话可以树状数组套主席树，时间复杂度相同，常数略大，空间O(nlogn)
当然这个模型感觉都快被写烂了...
D.注意到1阶回文是普通回文
而k阶回文决定了它一定也是回文，而且它也是1...k-1阶回文
想清楚了它的性质，就是个区间DP了
1 import java.util.Scanner; 2 3 public class D { 4 public static void main(String []args) { 5 Scanner cin = new Scanner(System.in); 6 int[][] dp = new int[5005][5005]; 7 int[] ans = new int[5005]; 8 String s = cin.nextLine(); 9 int n = s.length();10 for(int d = 1;d <= n;d ++)11 for(int i = 0;i + d - 1< n;i ++) {12 int j = i + d - 1;13 if(d < 3) dp[i][j] = (s.charAt(i) == s.charAt(j) ? d : 0);14 else if(s.charAt(i) != s.charAt(j) || dp[i + 1][j - 1] == 0) dp[i][j] = 0;15 else if(s.charAt(i) == s.charAt((i + j - 1) / 2)) dp[i][j] = dp[i][(i + j - 1) / 2] + 1;16 else dp[i][j] = 1;17 ans[dp[i][j]] ++;18 }19 for(int i = n - 1;i > 0;i --)20 ans[i] += ans[i + 1];21 for(int i = 1;i <= n;i ++)22 System.out.printf("%d ", ans[i]);23 }24 } 