codeforces心得1---747div2 codeforces心得1---747div2

codeforces心得1---747div2 【codeforces心得1---747div2】cf div2的前AB题一般是字符串or数论的找规律结论题
因此标程极为精简
1.小窍门是看样例或者自己打表或造数据找规律
2.一些不确定的操作，可以化成一种确定合法的操作比如：
div747 A的选择l 和 r的操作，这里的解是不确定的多个的，因此选择简单的且必然l加到r可以等于n的数，可以从数轴想到该数n>0时从l=1-n，r=n，n-1加到 1-n满足为0 总和为n，而n<0时l=n，r=-n-1，从n+1 到 -n-1为0，总和为n
div747C题，发现b 而字符串里面可能已经存在需要的字符，设位置为i，i之前的所有字符都会变成c(题目需要变成的字符)，当i>x/2的时候，2>x/i>1,则x不能整除i，且比x小的都不能，所以让i>n/2，就可以将所有的都变成c
3.即使发现了相同的规律，实现的代码的时候可以更加精练
div747B题，列数字可以看出，序列是n^0 n^1 n0+n1 n^2......
很像二进制的 0001 0010 0011 0100，正好对应该数是升序第几个，于是将k按照状态压缩，一位位取值然后相加
不过起始值是1，每过一位*n
精简前

#include #define MOD (int)(1e9 + 7) using namespace std; long long a[105], rec[105]; int n, k; int cal() { int chu = k, shang, yu = 0; do { shang = chu / 2; rec[++yu] = chu % 2; chu = shang; } while (shang); return yu; }int main() { int t; cin >> t; while (t--) { cin >> n >> k; int countn = cal(); long long sum = 0; a[1] = 1; for (int i = 2; i <= 35; i++) { a[i] = (a[i - 1] % MOD * n % MOD); // cout << a[i] << endl; } for (int i = 1; i <= countn; i++) { if (rec[i]) { sum += a[i]; sum %= MOD; } } cout << sum << endl; } return 0; }

精简后

#include #define MOD (int)(1e9 + 7) using namespace std; int main() { int n, k, t; cin >> t; while (t--) { cin >> n >> k; long long sum = 0, now = 1; while (k) { if (k & 1) { sum = (sum + now) % MOD; } k >>= 1; now = (now * n) % MOD; } cout << sum << endl; }return 0; }