judge: 牛客
A-A Simple Math Problem
judge:牛客
題意
給你一個n，讓你求出\(\sum_{i=1}^{n}\sum_{j=1}^{i}[gcd(i,j)==1]f(j)\)，
其中f(x)表示的是數位和，eg:f(122)=1+2+2=5，
題解
一眼可以看出是道反演題，但是仔細想想發現不是特別好維護，然后給的范圍又有點誤導，讓人以為可以瞎搞過（實際上真的可以打表過或者容斥過），然后中間耽擱了很長時間，還寫了個瞎搞的做法，不過沒敢交，最后才發現轉換一下就是一道經典的反演題，
首先題目讓我們求的是\(\sum_{i=1}^{n}\sum_{j=1}^{i}[gcd(i,j)==1]f(j)\)，我們需要轉換成\(\sum_{i=1}^{n}f(i)\sum_{j=i+1}^{n}[gcd(i,j)==1]\)，
其實只是列舉策略的變換，求的答案還是一樣，只不過第二個公式可以用反演求，而且還比較好求，第一個沒有辦法用反演做（其實是我不會），
至于原因，我們需要對第一個公式有足夠的了解，第一個公式讓我們求的是所有比當前數小，且與當前數互質的數的數位和，
思維轉換一下，我們把每個數單獨進行考慮，每個數對答案產生的貢獻就是比它大，且與它互質的數的個數乘以這個數的數位和（就是轉換后的公式），
至于第二個公式怎么求，可以參考我寫的一篇題解，這個題讓我們求的就是前半部分，只不過數位和變成了數位乘，
代碼
#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for (int i = (s); i <= (t); i++)
#define RP(i,t,s) for (int i = (t); i >= (s); i--)
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define dg if(debug)
#define outval(a) cout << "Debuging...|" << #a << ": " << a << "\n";
using namespace std;
int debug = 0;
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
return a/gcd(a,b)*b;
}
inline int read(){
int s=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
return s*f;
}
const int N = 1e6+7;
int n;
ll phi[N],mu[N];
int prime[N];
int flag[N];
ll F[N];
ll G[N];
ll Num[N];
int num=0;
int f(int x){
int ans=0;
while(x) ans+=x%10,x/=10;
return ans;
}
int g(int x){
int ans=1;
while(x) ans*=x%10,x/=10;
return ans;
}
void init(){
phi[1]=1;
mu[1]=1;
F[1]=G[1]=1;
for (int i=2;i<=n;i++){
F[i]=f(i);
G[i]=g(i);
if (flag[i]==0)//這代表i是質數
{
prime[++num]=i;
phi[i]=i-1;
mu[i]=-1;
}
for (int j=1;j<=num&&prime[j]*i<=n;j++){
flag[i*prime[j]]=1;
if (i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
mu[i*prime[j]]=0;
break;
}
phi[i*prime[j]]=phi[i]*(prime[j]-1),mu[i*prime[j]]=-mu[i];
}
}
rp(i,1,n) for(int j=i;j<=n;j+=i) Num[i]+=F[j];
}
void solve(){
n=read();
init();
ll ans1=0;
ll ans2=0;
rp(i,1,n){
ll t=0;for(int j=i;j<=n;j+=i) t+=F[j];
ans1+=mu[i]*t*(n/i);
}
rp(i,1,n) ans2+=F[i]*phi[i];
cout<<ans1-ans2+1<<endl;
}
int main(){
//ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef ONLINE_JUDGE
#else
freopen("in.txt", "r", stdin);
//debug = 1;
#endif
time_t beg, end;
//if(debug) beg = clock();
solve();
/*
if(debug) {
end = clock();
printf("time:%.2fs\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}
*/
return 0;
}
B-Apple
judge:牛客
題意
現有n個蘋果，求出能否分給m個人，滿足所有人的蘋果總數都不一樣，
題解
首先求出滿足m個人的蘋果數量都不同的最少蘋果數，最實惠的方案當然是依次擁有1,2,3,...,m-1,m個蘋果，需要花費\(\frac{m(m+1)}{2}\)個蘋果，至于剩下的蘋果，全部交給最后一個人即可，這樣就滿足了所有人的蘋果數都不一樣，
如果蘋果總數小于\(\frac{m(m+1)}{2}\)，就說明無論怎么分都無法滿足每個人的蘋果總數都不一樣，
代碼
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); }
return s * f;
}
void solve() {
int n = read(), m = read();
if (n >= m * (m + 1) / 2) puts("possible");
else puts("impossible");
}
int main() {
int T = read();
while (T--) solve();
return 0;
}
E-Color Sequence
judge:牛客
題意
定義一個合法的序列為序列里的每個元素都出現偶數次，
給定一個有n個元素的序列，序列元素最多有21種，編號在數值在[0-20]，求出合法序列的個數，
題解
維護每個數字出現次數的前綴和，且我們只關心數字出現次數的奇偶性，所以我們只保存 \(0\) 和 \(1\) 兩個狀態，一個二進制位即可保存一個數字的狀態，將 \(21\) 個前綴和的對應位置歸納到一起，那么一個 \(int\) 型別的整數就可保存一組狀態，
當一組狀態為 \(t\) 時，維護每組狀態出現的次數 \(num[t]\)，
假設 \(a_i\) 為 \(2\)，前一個位置的狀態為 \(t\)，那么將 \(a_i\) 加入 \(t\)，只需要將 \(t\) 中的第 \(i\) 個位置取反，即 \(t=t\oplus(1<<a_i)\)，然后將 \(num[t]=num[t]+1\)，
假設將 \(a_i\) 加入后的狀態為 \(t\)，則前面有 \(num[t]\) 個位置可以作為起點，第 \(i\) 個位置作為終點，區間內所有元素的出現次數都為偶數，
\[ans=\sum_{i=1}^{n}{num[t_i]} \]代碼
#include <bits/stdc++.h>
#define _for(i, a) for(int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for(int i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;
typedef long long LL;
const int maxn = 100005;
const int maxm = 5000005;
const int inf = 0x3f3f3f3f;
inline int read() {
int x(0), f(1); char ch(getchar());
while (ch<'0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
int n;
int mp[maxm];
void sol() {
int t = 0;
int ans = 0;
++mp[t];
_rep(i, 1, n) {
int x = read();
t ^= (1 << x);
ans += mp[t];
++mp[t];
}
printf("%d\n", ans);
}
int main() {
n = read();
sol();
return 0;
}
G-Mathematical Practice
judge:牛客
題意
題意不詳...
題解
隊友一眼看出答案是 \((m+1)^n\)...
代碼
#include <bits/stdc++.h>
#define _for(i, a) for(register int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for(register int i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;
typedef long long LL;
const int mod = 998244353;
inline int read() {
int x(0), f(1); char ch(getchar());
while (ch<'0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
LL quickPow(LL x, LL n, LL mod) {
LL ans = 1;
while(n) {
if(n & 1) ans *= x, ans %= mod;
x *= x, x %= mod;
n >>= 1;
}
return ans;
}
int main() {
LL n = read(), m = read();
printf("%lld\n", quickPow(m + 1, n, mod));
return 0;
}
H-Sequence
judge:牛客
題意
給你一個每個元素都互不相同的長度為 \(n\) 的序列.
定義兩種操作:
- 選擇一個元素 \(a_x\), 令 \(a_x=y\).
- 選擇一個元素 \(a_x\), 找出最小值為 \(a_x\) 的子串的個數.
題解
考慮分塊維護每個塊的最小值.
- 當執行操作1時, 令 \(a_x=y\), 同時重新計算 \(a_x\) 所在的塊的最小值.
- 當執行操作2時, 分別找出左右兩邊連續大于等于 \(a_x\) 的元素的個數, 例如
134562中4左右分別有1和2個不小于4的元素. 那么可以計算出包含4的子串的數目為 \(1+2+1\times 2+1=6\), 當左邊有 \(cl\) 個元素,右邊有 \(cr\) 個元素時,包含 \(a_x\) 的字串的數目為 \(cl+cr+cl\times cr+1\).
代碼
#include <bits/stdc++.h>
#define _for(i, a) for(LL i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for(LL i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;
typedef long long LL;
const LL maxn = 100005;
inline LL read() {
LL x(0), f(1); char ch(getchar());
while (ch<'0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
LL a[maxn], k[maxn], len;
LL n, m;
LL getN(LL pos) {
return (pos - 1) / len + 1;
}
void init() {
len = sqrt(n) + 1;
len = min(len, n);
}
LL getLValOfThis(LL pos) {
LL nu = getN(pos);
for(LL i = pos - 1; i > (nu - 1) * len; --i) if(a[i] < a[pos]) return i;
return -1;
}
LL getRValOfThis(LL pos) {
LL nu = getN(pos);
for(LL i = pos + 1; i <= nu * len; ++i) if(a[i] < a[pos]) return i;
return -1;
}
LL getLVal(LL pos) {
LL nu = getN(pos);
for(LL i = nu - 1; i > 0; --i) if(k[i] < a[pos]) return i;
return -1;
}
LL getRVal(LL pos) {
LL nu = getN(pos), mn = getN(n);
for(LL i = nu + 1; i <= mn; ++i) if(k[i] < a[pos]) return i;
return -1;
}
void sol() {
init();
_rep(i, 1, n) a[i] = read();
LL mn = getN(n);
_rep(i, 1, mn) k[i] = LLONG_MAX;
_rep(i, 1, n) k[getN(i)] = min(k[getN(i)], a[i]);
_for(i, m) {
LL op = read();
if(op == 1) {
LL x = read(), val = read();
LL nu = getN(x);
a[x] = val;
k[nu] = LLONG_MAX;
for(LL i = (nu - 1) * len + 1; i <= nu * len; ++i) k[nu] = min(k[nu], a[i]);
}
else {
LL pos = read();
LL l = pos - 1, r = pos + 1;
LL cl = 0, cr = 0;
LL LThis = getLValOfThis(pos);
if(LThis != -1) cl = pos - LThis - 1; // 本塊內找到
else { // 本塊內未找到，從下一塊開始找
LL nu = getLVal(pos);
if(nu == -1) cl = pos - 1; // 左邊沒有比a[pos]更小的
else { // 左邊有比a[pos]更小的
cl = pos - nu * len - 1;
for(LL i = min(pos - 1, nu * len); i > 0 && a[i] > a[pos]; --i) {
cl = pos - i;
}
}
}
LL RThis = getRValOfThis(pos);
if(RThis != -1) cr = RThis - pos - 1; // 本塊內找到
else { // 本塊內未找到，從下一塊開始找
LL nu = getRVal(pos);
if(nu == -1) cr = n - pos; // 右邊沒有比a[pos]更小的
else { // 右邊有比a[pos]更小的
cr = (nu - 1) * len - pos;
for(LL i = max(pos + 1, (nu - 1) * len + 1); i <= n && a[i] > a[pos]; ++i) {
cr = i - pos;
}
}
}
LL ans = cl + cr + cl * cr + 1;
printf("%lld\n", ans);
}
}
}
int main() {
n = read(), m = read();
sol();
return 0;
}
I-Simple Math Problem
judge:牛客
題意
給你一個 \(n\times n\) 的矩陣,其數字的排布方式如下:
0 1 3 6 10
2 4 7 11 15
5 8 12 16 19
9 13 17 20 22
14 18 21 23 24
求出第 \(x\) 行第 \(y\) 列的元素的值. 注意\((0≤x≤1000000000, 0≤y≤1000000000, 1≤n≤1000000001)\).
題解
旋轉一下矩陣:
0
2 1
5 4 3
9 8 7 6
14 13 12 11 10
18 17 16 15
21 20 19
23 22
24
那么第 \(x\) 行第 \(y\) 列就對應第 \(x+y-1\) 行. 假設 \(r=x+y-1\).
- 當 \(x+y<=n\) 時, 先算出前 \(r-1\) 行的數字個數 \(1+2+...+r-1\), 等引數列求和: \(\frac{r(r-1)}{2}\), 再加上 \(r\) 行剩下的 \(x\) 個數, 由于題目從0開始,所以為 \(\frac{(x+y-1)(x+y-2)}{2}+x-1\).
- 當 \(x+y-1>n\) 時, 同樣利用上面的規律算出下面得數字個數,然后拿 \(n\times n\) 減去個數即可. 假設 \(x' = n - x + 1, y' = n - y + 1\) , \(a[x][y]\) 后面的數字個數為 \(\frac{(x'+y'-1)(x'+y'-2)}{2}+x'-1\), 那么 \(a[x][y]\) 就是正向的第 \(n\times n-\frac{(x'+y'-1)(x'+y'-2)}{2}-x'+1\) 個數, 從0開始就是 \(n\times n-\frac{(x'+y'-1)(x'+y'-2)}{2}-x'\)
代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read() {
int x(0), f(1); char ch(getchar());
while (ch<'0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
int main() {
LL n = read(), x = read() + 1, y = read() + 1, ans = 0;
if(x + y <= n + 1) {
ans = (x + y - 1) * (x + y - 2) / 2 + x - 1;
}
else {
LL _x = n - x + 1, _y = n - y + 1;
ans = (_x + _y - 1) * (_x + _y - 2) / 2 + _x;
ans = n * n - ans;
}
printf("%lld\n", ans);
return 0;
}
K-Travel Expense
judge:牛客
待補，，
M-Zoos's Animal Codes
judge:牛客
題意
簽到題
每個園子有個園子號,每個動物有個動物號,合起來就是動物編號.
給出園子號和動物號,求出動物編號.
題解
無
代碼
#include <bits/stdc++.h>
using namespace std;
int main() {
string a, b;
cin >> a >> b;
cout << a << b;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/249742.html
標籤：其他
下一篇：力扣刷題（35. 搜索插入位置）