传送
A题 因数个数和
文章图片
文章图片
例如n=10，那么从1，到10所有数字都含因子12，4，6，8，10含因子23，6，9含因子3依次类推
枚举不同因子计算加和
#include
#define repu(i,s,e) for(int i = s;
i <= e;
++i)
#define repd(i,s,e) for(int i = s;
i >= e;
--i)
#define pb push_back
#define emb emplace_back
#define mst(arr, v) memset(arr, v, sizeof(arr))
#define close_ios ios::sync_with_stdio(false)
#define close_cin cin.tie(0)
#define close_cout cout.tie(0)
#define ct(a) cout<>T;
while(T--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair Pa;
typedef vector Ve;
const double PI = acos(1.0);
const double eps = 1e-8;
int dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 5;
const int M = 100 + 5;
const int mod = 1e9 + 7;
int main()
{
Repeat{int n;
ll ans = 0;
sf1(n);
int pos;
for(int i = 1;
i <= n;
i = pos + 1)
{
pos = n / (n / i);
ans += 1LL * (pos - i + 1) * (n / i);
}
ct(ans);
}
return 0;
}
B题
（开始我竟然想的是m次LIS。。 ）
记录下所有的值a[i], 设置一个数组 f 记录 第i个所长最长序列的长度再设置一个数组cnt 记录长度为f[i]的有多少个
询问时直接从100往小找即可，题中明确ai小于100所以最大长度不超过100
【牛客网|牛客练习赛25】每次修改影响a[x]的值 及影响f[x] 及以后的 min(x+100,n)项原来的f[i]的数量要减1后来f[i] 要加1
#include
#define repu(i,s,e) for(int i = s;
i <= e;
++i)
#define repd(i,s,e) for(int i = s;
i >= e;
--i)
#define pb push_back
#define emb emplace_back
#define mst(arr, v) memset(arr, v, sizeof(arr))
#define close_ios ios::sync_with_stdio(false)
#define close_cin cin.tie(0)
#define close_cout cout.tie(0)
#define ct(a) cout<>T;
while(T--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair Pa;
typedef vector Ve;
const double PI = acos(1.0);
const double eps = 1e-8;
int dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 5;
const int M = 100 + 5;
const int mod = 1e9 + 7;
int n, m, a[N], f[N], cnt[M];
int query()
{
repd(i,100,1)
if(cnt[i]) return i;
return 0;
}
int main()
{
sf2(n, m);
repu(i,1,n)
{
sf1(a[i]);
if(a[i] > a[i - 1]) f[i] = f[i - 1] + 1;
else f[i] = 1;
cnt[f[i]] ++;
}ct(query());
int x, y;
while(m --)
{
sf2(x,y);
a[x] = y;
repu(i,x,min(x+100,n))
{
int t = 1;
if(a[i] > a[i - 1])
t = f[i- 1] + 1;
cnt[f[i]] --;
f[i] = t;
cnt[f[i]]++;
}ct(query());
}return 0;
}
线段树做法：
#include
#define repu(i,s,e) for(int i = s;
i <= e;
++i)
#define repd(i,s,e) for(int i = s;
i >= e;
--i)
#define pb push_back
#define emb emplace_back
#define mst(arr, v) memset(arr, v, sizeof(arr))
#define close_ios ios::sync_with_stdio(false)
#define close_cin cin.tie(0)
#define close_cout cout.tie(0)
#define ct(a) cout<>T;
while(T--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair Pa;
typedef vector Ve;
const double PI = acos(1.0);
const double eps = 1e-8;
int dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 5;
const int M = 100 + 5;
const int mod = 1e9 + 7;
int n, m;
int a[N];
int lsum[N<<2], rsum[N<<2], msum[N<<2];
void pushup(int l,int r,int rt)
{
int m = (l+r)>>1;
lsum[rt] = lsum[rt<<1];
rsum[rt] = rsum[rt<<1|1];
msum[rt] = max(msum[rt<<1], msum[rt<<1|1]);
if(a[m] < a[m+1]) //如果左区间的右端小于右区间的左端
{
if(lsum[rt<<1] == m - l + 1) //如果左区间全部为上升序列
lsum[rt] = lsum[rt<<1] + lsum[rt<<1|1];
if(rsum[rt<<1|1] == r - m)//如果右区间全部为上升序列
rsum[rt] = rsum[rt<<1] + rsum[rt<<1|1];
msum[rt] = max(msum[rt], lsum[rt<<1|1] + rsum[rt<<1]);
}
}void build(int l,int r,int rt)
{
if(l == r)
{
lsum[rt] = rsum[rt] = msum[rt] = 1;
return ;
}int m = (l+r)>>1;
build(lson);
build(rson);
pushup(l,r,rt);
}void update(int p,int c,int l, int r,int rt)
{
if(l == r)
{
a[p] = c;
return ;
}int m = (l+r)>>1;
if(p <= m)
update(p,c,lson);
else
update(p,c,rson);
pushup(l,r,rt);
}int query(int L,int R,int l,int r,int rt)
{
if(l >= L && R >= r)
return msum[rt];
int ret = 0;
int m = (l+r)>>1;
if(L <= m) ret = max(ret, query(L,R,lson));
if(R > m) ret = max(ret, query(L,R,rson));
//如果左区间的右端小于右区间左端
if(a[m] < a[m + 1])
ret = max(ret, min(m - L + 1, rsum[rt<<1]) + min(R - m, lsum[rt<<1|1]));
return ret;
}int main()
{
sf2(n, m);
repu(i,1,n)
sf1(a[i]);
build(1,n,1);
ct(query(1,n,1,n,1));
while(m --)
{
int x, y;
sf2(x, y);
update(x,y,1,n,1);
ct(query(1,n,1,n,1));
}
return 0;
}
C题
看例子，四项和是 10而第一次变换之后是 前一次变换的和 减去当前位置的值
第二次变换时，起始是20 + a[i]而 20 = (n - 1)*change[i-1] - 没有变换时的值
以此类推，你会发现他是一个等比数列，加减原来的值与变换的次数有关系
（逻辑混乱。。。）
下面贴一下官方的解
文章图片
#include
#define repu(i,s,e) for(int i = s;
i <= e;
++i)
#define repd(i,s,e) for(int i = s;
i >= e;
--i)
#define pb push_back
#define emb emplace_back
#define mst(arr, v) memset(arr, v, sizeof(arr))
#define close_ios ios::sync_with_stdio(false)
#define close_cin cin.tie(0)
#define close_cout cout.tie(0)
#define ct(a) cout<>T;
while(T--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair Pa;
typedef vector Ve;
const double PI = acos(1.0);
const double eps = 1e-8;
int dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 5;
const int M = 100 + 5;
const int mod = 1e9 + 7;
int n, m;
int a[N];
ll ans[N];
int main()
{
ll s = 0;
sf2(n, m);
repu(i,1,n)
sf1(a[i]), s += a[i], s%= mod;
s %= mod;
ans[1] = s;
repu(i,2,1e5)
{
if(i&1)
ans[i] = ((n - 1) * ans[i - 1] % mod + s + mod)% mod;
else
ans[i] = ((n - 1) * ans[i - 1] % mod - s + mod)% mod ;
}int p, t;
repu(i,1,m)
{
sf2(p,t);
if(!t)
{
ct(a[p]);
continue;
}if(t&1)
ct((ans[t] - a[p] + mod)%mod);
else
ct((ans[t] + a[p] + mod)%mod);
}
return 0;
}
