2020威海CCPC D，思维训练
ABC Conjecture
题意：给定一个数c，请你判断是否存在这样的两个数a和b，满足a+b=c，并且abc的质因子的乘积小于c(重复的质因子视为一个)。
思路：我首先发现对于这个题来讲，第一个条件基本没用，重点在于第二个条件，只要满足第二个条件就可以了，那么怎么满足呢？
发现当c的质因子出现重复的时候，c的所有种类质因子的乘积一定是小于c的，同时可以根据这些质因子来创两个数，使得这两个数的和等于c，所以问题转变为判断c是有某个质因子出现重复。那么重复是什么？也就是平方，立方，四次方等等，最简单的方式就是平方，只要判断一个数能否被某个平方数整除即可。
但是问题来了，1e18这么大，处理平方数是1e9个显然不是可以接受的（通常视一秒1e7为复杂度的极限)
但是我们可以处理1e12范围内的平方数，如果给定的c可以整除那么直接就是yes的判定，否则的话考虑一下是什么情况
如果这个数是个平方数，但是过大，必然是某个因子乘上了这个平方数，使得无法判断，那么我们只需要剔除c的1e6范围内的所有质因子即可。剔除后再判断是否为平方数。
值得注意的是c为1需要特判，否则会WA27
#include
using namespace std;
#define int long long
#define endl '\n'
const int N = 1e7+100;
const int te=1e9;
int super_sqrt(int x)
{int l=1,r=sqrt(x+100),ans=0;while(l<=r){int mid=(l+r)>>1;if(mid*mid<=x) ans=mid,l=mid+1;else r=mid-1;}return ans;
}
bool isPrime[N];
int Prime[N],cnt=0;
void GetPrime(int n)
{isPrime[1]=0;for(int i=2;i<=n;i++){if(isPrime[i]){Prime[++cnt]=i;}for(int j=1;j<=cnt&&i*Prime[j]<=n;j++){isPrime[i*Prime[j]]=0;if(i%Prime[j]==0){break;}}}
}
signed main()
{//cout<<998244353ll*998244353ll< p;for(int i=2;i*i<=100000000000000;i++)p.push_back(i*i);int t;for(cin>>t;t;t--){int n;cin>>n;if(n==1){cout<<"no\n";continue;}bool falg=false;for(auto x:p)if(n%x==0)falg=true;for(int i=1;i<=cnt;i++){int con=0;while(n%Prime[cnt]==0){n/=Prime[cnt];con++;}if(con>=2){falg=true;}}if(super_sqrt(n)*super_sqrt(n)==n){falg=true;}if(falg)cout<<"yes";elsecout<<"no";if(t!=1)cout< C. Inversion Graph
这个思维题还是很6的。
给定了一个排列，对于所有逆序对都连边，问你总共几个连通块。
思路：我们如果想用dsu去做的话，可能就需要对所有的连边都处理，但是最多可能会达到n*(n+1)/2条，所以复杂度不好实现。
从排列角度考虑，如果是正序情况，那么对于i来讲，i位置的前缀和就是i(i+1)/2，但是正序情况下就是n个连通块，也就是没有边相连，对于题目反向思考，如果截至到某个位置的前缀和是i(i+1)/2那么是不是就可以理解为多了一个连通块呢？显然是可以的。
#include
using namespace std;
int T,n,a[100005],ans=0;
long long sum=0;
int main()
{cin>>T;for(int i=1;i<=T;i++){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];//sum前缀和 if(sum==1LL*(1+i)*i/2)ans++;}cout< M - Function and Function
青岛的一个签到，大概是考了一个类似数字空洞的东西，其实可以发现递归到10层后基本就变为奇偶规律了。
#include using namespace std;int a[10]={1,0,0,0,1,0,1,0,2,1};
int x,k;
pair f(int x,int k)
{if(k==0||x==0){return make_pair(k,x);}int res=0;while(x){res+=a[x%10];x/=10;}f(res,k-1);
}
int main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t;for(cin>>t;t;t--){cin>>x>>k;auto n=f(x,k);if(n.first==0){cout<if(n.first%2){cout<<(n.second^1)<cout< J - Books
脑筋急转弯？
这个题需要注意的是，其实他价格为0的书我们只算其为应得数量，但是这种书和实际获得与钱数都没有什么关系，这样考虑。
#include
#include
#define ll long long
#define INF 1000000007
using namespace std;
int main()
{int T,n,m,x;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);vectorv;for(int i=1; i<=n; ++i){scanf("%d",&x);if(x!=0)v.push_back(x);}int len=v.size();int zero=n-len;if(mm-=zero;ll sum=0;int t=INF;for(int i=0; iif(i+1<=m)sum+=v[i];else t=min(t,v[i]);}sum+=t-1;printf("%lld\n",sum);}}return 0;
}