A - AtCoder Quiz 3
B - Triple Metre
C - X drawing 暫無
D - Destroyer Takahashi 暫無 貪心好難啊
E - Fraction Floor Sum
F - Predilection
G - GCD Permutation
H - Bullion無

$A$

int t;scanf("%d", &t);t += t>=42;printf("AGC%03d", t);

$B$

string t = "", c;for(int i = 1;i <= 20;i ++)t += "oxx";cin>>c;puts(t.find(c)<t.length()?"Yes" :"No");

$E$? 分塊模板

LL sum = 0, n;scanf("%lld", &n);for(LL l = 1, r;l <= n;l = r+1){r = n/(n/l);sum += (r-l+1)*(n/l);}cout<<sum<<endl;

$F$?考慮dp, $dp[i]$ 表示把1~i劃分的方案數，那么$dp[i]=dp[i?1]?2$ (相當于把 $i?1$的方案數后面都加上 $num[i]$) 但這樣有重復的, 重復的是前綴和相等的那部分，這個是我照著樣例看的，就是這個思路。。容斥了半天結果發現之前思路錯了

int n, ans = 0, l = 0; // 考慮dp, dp[i]代表 前i個數的答案 LL sum = 0;scanf("%d", &n);for(int i = 1;i <= n;i ++){int x;scanf("%d", &x);l = ans;if(i != 1) add(ans, ans-ma[sum]);else add(ans, 1);ma[sum] = l; }add(ans, mod);cout<<ans<<endl; /*0 1 377914575 2 102436426 4 102436426 6 -341739478 12 377914575 23 123690081 46 0 92 377914575 172 123690081 321*/

$G$?有個枚舉i的思想，但是pi不會算了，看了答案說這部分枚舉可以優化具體來說就是${\sum }_{u=1}^n{\sum }_{v=1}^{n}c[u]?c[v]?C_{num}^2$
?其中num是滿足 $u|i$&&$v|p[i]$ 的數量, 在考慮容斥如果你算了$u=a?b$ 的話，那么$a^2?b$ 也被算了，但如果你算了$u=a，u=b$ 的話 $u=a?b$被多算了，然后題解就給了個式子，如果u 可以表示乘不同的質數的乘積的話那么他是有效的，并且如果他是奇數個質數的乘積的話是要加上的，偶數個質數的乘積的話是要減去的，v的話同理
?上面都是前情提要下面是化簡部分不化簡得話是n² 的，思路就是那個對固定的u來說v只有是不同的質數的乘積的話才有效，不同的質數對 $p[i]$ 來說，v的個數就很小了，至多63個，那么可以對每個$p[i]$求出可以整除的v。下來再進行計算，沒看懂看看代碼吧。

int p[N]; vector<int>v[N]; int c[N], num[N];int main() {int n;scanf("%d", &n);for(int i = 1;i <= n;i ++) scanf("%d", p+i); for(int i = 2;i <= n;i ++) // 這個for 是干 求出 c[u] 和每個p[i] 可以整除的v的 ;{int a[10], idx = 0, t = i, flag = 1;for(int x = 2;x <= t/x;x ++)if(t%x == 0){t /= x; while(t%x == 0) flag = 0, t /= x;a[idx++] = x;}if(t != 1) a[idx++] = t;c[i] = flag ? (idx%2 ? 1 : -1) : 0; // flag = 0 代表不是不同的質數的乘積。 for(int _ = 1, m = 1;_ < 1<<idx;v[i].push_back(m), m = 1, _ ++) // 枚舉質數的選擇，v[i]保存對應的可整除的v； for(int j = 0;j < idx;j ++)if(_>>j&1)m *= a[j];} LL ans = 0;for(int i = 2;i <= n;i ++) {if(!c[i]) continue;debug語句 // cout<<i<<" ++ "<<endl; for(int j = i;j <= n;j += i)for(auto x : v[p[j]])num[x] ++;for(int j = i;j <= n;j += i)for(auto x : v[p[j]])if(num[x]) ans += (LL)c[i]*c[x]*num[x]*(num[x]-1)/2, num[x] = 0;debug語句 // cout<<x<<' '<<num[x]<<' '<<c[i]<<' '<<c[x]<<endl, }ans += p[1] == 1 ? n-1 : n-2; // 還有自己和自己 上面的都是C(n,2), 是不同的數的選擇， cout<<ans<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的AtCoder Beginner Contest 230的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。