------------恢复内容开始------------
D - Together Square
这道题很有意思吧！ 打表去OEIS查 查到一串天文 最后还是想了一下性质 平方数是不是分解质因数都是偶的 那我们记录质因数奇数的就好了 然后奇数的可以和奇数的拼一起就是偶数的了 并且我们枚举每一个都是全排列
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 1<<10;
const int mod = 1e9+7;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int fun(int n){
int res=1;
for(int i=2;i<=n/i;i++){
if(n%i==0){
int cnt=0;
while(n%i==0){
n/=i;
cnt++;
}
if(cnt%2){
res*=i;
}
}
}
if(n>1)res*=n;
return res;
}
void solve() {
int n;cin>>n;
map<int,int>mp;
for(int i=1;i<=n;i++){
int t=fun(i);
mp[t]++;
}
int ans=0;
for(auto p:mp)ans+=p.second*p.second;
cout<<ans<<endl;
}
signed main(){
fast
solve();
return ~~(0^_^0);
}
D. Chip Move
其实有时候直觉挺重要的 我好像知道是个dp 却无从下手 打表看了下发现也没啥思路 咋办？？？
其实更重要的是相信自己的直觉 我们就比如他是个dp 然后我们咋设计状态 由题意得 我们一维要表示步数 一维要表示当前在第几个位置 （其实这里我们很容易想到刷表的方式去暴力枚举 正难则反嘛 我们可以递推的去让他做道线性复杂度 因为我们都是有顺序的 希望自己下次能反应过来www
而且 k+1 必须由 k 转移过来 那我们的f[i][j]就表示在第i（从k开始枚举）步 我们在第j个位置的cnt
但是这是n2的 咋办？？？ 我们仔细想一下 好像是有上届的是吧 我们最坏k=1开始 1+2+3+4+5+...+t=n 那我们t也只是个根号级别的
所以时间复杂度是根号n*n的
好我们继续想状态计算：f[i][j]=f[i-1][j-i]+f[i][j-i] 好像这样确实做到不重不漏了
最后我们再用个滚动数组优化即可 记住我们是要求每一个位置的cnt 所以每一步都要加上去 初始化就是f[k]=1;
其实转念一想 这应该抽象成一个完全背包 我们每次都可以拿无限个i进去（如果能观察出这一点的 dp 和 状态转移都很一眼了
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
void solve() {
int n,k;cin>>n>>k;
vector<int>b(n+10),ans(n+10),f(n+10);
f[k]=1;
int nw=k;
for(int i=k;nw<=n;i++){
for(int j=i;j<=n;j++){
f[j]=(f[j]+b[j-i]+f[j-i])%mod;
}
nw+=i;
b=f;
for(int j=1;j<=n;j++){
ans[j]=(ans[j]+f[j])%mod;
f[j]=0;
}
}
for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
}
signed main(){
fast
solve();
return ~~(0^_^0);
}
D. Required Length
我也是第一次真见到搜索题 我看了一眼范围 感觉每层最坏只要80层 然后分支也最多就10 感觉数据范围是可做的
然后随便写了一个T了
最后想了一下一个预见性的剪枝 就是我们最多每一次+1位 我们当前位贪心每次都加1位再与res比较即可
后面看了题解有IDA* 感觉也是很正确的启发式函数就是n-当前位 哦 原来就是和我这个剪枝一样啊！
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int n,x,res=inf;
void dfs(int m,int ans){
if(ans>=res)return;
vector<int>v;
int cnt=m;
while(cnt)v.push_back(cnt%10),cnt/=10;
if(n-v.size()+ans>=res)return;
if(v.size()==n){
res=min(res,ans);
}
int flag1=0;
for(auto i:v)if(i!=1&&i!=0)flag1=1;
if(!flag1)return;
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
for(int i=v.size()-1;i>=0;i--){
dfs(m*v[i],ans+1);
}
}
void solve() {
cin>>n>>x;
dfs(x,0);
if(res==inf)cout<<-1<<endl;
else cout<<res<<endl;
}
signed main(){
fast
//int T;cin>>T;
//while(T--) {
solve();
// }
return ~~(0^_^0);
}
CF1661B Getting Zero
警惕记忆化搜索不能有%操作 不然会成环 警惕CF不能打表
观察出来了每次<<1 所以最多15次 但是有加法咋办 感觉想了几个情况还是挺麻烦的 不如暴力吧 算算O（N1515）才3百万 那没事了那没事了 //今天居然solved2
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 32768;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int lowbit(int x){return x&-x;}
void solve() {
int n;cin>>n;
int res=inf;
for(int j=0;j<=15;j++) {
int t=lowbit(n+j);
if(t>=1<<15||!t){res=min(res,j);continue;}
for (int i = 0; i < 15; i++) {
if (t >> i & 1)res=min(res,15-i+j);
}
}
cout<<res<<' ';
}
signed main(){
fast
int T;cin>>T;
while(T--) {
solve();
}
return ~~(0^_^0);
}
G. Count the Trains
我们知道这个是肯定是单调递减的 所以可以用二分
我们先预处理好每个火车头的编号 放进一个set里面正好set也是单调的
然后我们对于每次更新 就是看其能不能小于他的火车头 要是能小于 他将自成一个火车头 并且还会改变后面的火车头
咋做呢？？？
暴力的话好像是可以的 因为我们最多本来就有n个头 插入m个 那删除不可能删>n+m 所以暴力也是O（nlog）
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int M = 998244353;
const int mod = 32768;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n + 1);
set<int> s;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
if (s.empty())s.insert(i);
else if(a[*s.rbegin()] > a[i])s.insert(i);
}
while (m--) {
int j, c;
cin >> j >> c;
a[j] -= c;
auto it = s.upper_bound(j);
if (it != s.begin()) {
it = prev(it);
if (a[*it] > a[j])s.insert(j);
}
while (1) {
it = s.upper_bound(j);
if (it != s.end() && a[*it] >= a[j])s.erase(it);
else break;
}
cout << (int) s.size() << ' ';
}
cout << endl;
}
signed main(){
int T;cin>>T;
while(T--) {
solve();
}
return ~~(0^_^0);
}
CF1690E Price Maximization
很容易发现这是%后 再贪心就是了 但是我最开始写的一个t了 应该是我拿l来贪复杂度高了
那我们可以拿高位来贪只要满足r的l 然后就可以一只往后走 只用扫一遍 最后记得处处判l<r
要是拿l来贪 就要考虑先从k-l 开始扫 感觉常数有点大！
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int M = 998244353;
const int mod = 32768;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
void solve() {
int n,k,ans=0;cin>>n>>k;
vector<int>a(n),b(n);
for(int i=0;i<n;i++){
cin>>a[i];
ans+=a[i]/k;
b[i]=a[i]%k;
}
sort(b.begin(),b.end());
int l=0,r=n-1;
while(l<r){
while(b[l]+b[r]<k&&l<r)l++;
if(b[l]+b[r]>=k&&l<r)ans++,l++,r--;
else break;
}
cout<<ans<<endl;
}
signed main(){
fast
int T;cin>>T;
while(T--) {
solve();
}
return ~~(0^_^0);
}
F. Shifting String
对于每个置换 我们可以将其分成很多个环 以往环都是确定的数 但这道题不同的是有了字母 那我们就可以用链表模拟这个置换因为我们每次置换不会超过n 时间复杂度最坏的O（n2）的
当模拟的now==pre就直接和求一次lcm就行了
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 32768;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int p[N],n,vis[N];
string s;
vector<int>c;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;}
void dfs(int u){
if(vis[u])return;
vis[u]=1;
c.push_back(u);
dfs(p[u]);
}
void solve() {
cin>>n>>s;s=")"+s;
for(int i=1;i<=n;i++)cin>>p[i],vis[i]=0;
int ans=1;
for(int i=1;i<=n;i++){
if(!vis[i]){
c.clear();
dfs(i);
list<char>pre,now;
for(auto id:c)pre.push_back(s[id]);
now=pre;
now.push_back(now.front());now.pop_front();
int res=1;
while(pre!=now){
now.push_back(now.front());now.pop_front();
res++;
}
ans=lcm(ans,res);
}
}
cout<<ans<<endl;
}
signed main(){
fast
int T;cin>>T;
while(T--) {
solve();
}
return ~~(0^_^0);
}