A：注意9和1的特判。
1 #include<stdio.h> 2 #define it register int 3 #define il inline 4 int a,b; 5 int main(){ 6 scanf("%d%d",&a,&b); 7 if(a^b){ 8 if(a+1==b) return printf("%d %d",a,b),0; 9 if(a==9&&b==1) return printf("%d9 %d00",a,b),0; 10 printf("-1"); 11 return 0; 12 } 13 if(a==0&&b==0) return puts("-1"),0; 14 printf("%d1 %d2",a,b); 15 return 0; 16 }
B：线性扫描，控制长度为d即可.
1 #include<stdio.h> 2 #define it register int 3 #define il inline 4 #define Min(a,b) (a<b?a:b) 5 const int N=1000005; 6 int T,n,d,a[N],k,cn[N],ans; 7 il void fr(int &num){ 8 num=0;char c=getchar();int p=1; 9 while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar(); 10 while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar(); 11 num*=p; 12 } 13 int main(){ 14 fr(T); 15 while(T--){ 16 fr(n),fr(k),fr(d),ans=0; 17 for(it i=1;i<=n;++i) fr(a[i]); 18 for(it i=1;i<=d;++i) ans+=(!cn[a[i]]),++cn[a[i]]; 19 for(it i=1,now=ans;i+d<=n;++i){ 20 if(!--cn[a[i]]) --now; 21 if(!cn[a[i+d]]++) ++now; 22 ans=Min(ans,now); 23 } 24 if(n<k) for(it i=1;i<=n;++i) cn[a[i]]=0; 25 else for(it i=0;i<=k;++i) cn[i]=0; 26 printf("%d ",ans); 27 } 28 return 0; 29 }
C：移项，枚举n-p*d，检查是否可行即可。由于可以有重复的，记录一下最多和最少分解的个数，只要minn<=d<=maxn就是可行解。
1 #include<stdio.h> 2 #define it register int 3 #define il inline 4 const int N=100005; 5 typedef long long ll; 6 ll pw[N],n,p; 7 bool ck(ll x,it d){ 8 it now=0; 9 ll now2=0; 10 for(it i=62;i>=0;--i) if(x>=pw[i]) x-=pw[i],++now,now2+=pw[i]; 11 return now<=d&&now2>=d; 12 } 13 int main(){ 14 pw[0]=1ll;for(it i=1;i<=62;++i) pw[i]=pw[i-1]<<1ll; 15 scanf("%lld%lld",&n,&p); 16 for(it i=1;n>p*i&&i<=10000;++i) 17 if(ck(n-p*i,i)) return printf("%d",i),0; 18 puts("-1"); 19 return 0; 20 }
D：考虑n=a1p1*a2p2*……*anpn 。那么我们只要求出n=a1(k-p1)*a2(k-p2)*……*an(k-pn) *x1k *x2k *……*xnk是否存在就可以了。先把前面的算出来，hash一下。
1 #include<stdio.h> 2 #include<vector> 3 #include<map> 4 #include<algorithm> 5 #define it register int 6 #define il inline 7 #define Max(a,b) (a<b?a:b) 8 using namespace std; 9 typedef long long ll; 10 const int N=100002; 11 int a[N],p[N],minp[N],pri[N],cnt,k,n,pos; 12 bool pr[N]; 13 vector<pair<int,int> > g[N],vec; 14 map<vector<pair<int,int> > ,ll> mp; 15 ll ans; 16 il void prime(){ 17 register ll x;minp[1]=1; 18 for(int i=2;i<=N;i++){ 19 if(!pr[i]) pri[++cnt]=i,minp[i]=i; 20 for(int j=1;(x=1ll*i*pri[j])<=N&&j<=cnt;j++){ 21 pr[x]=true,minp[x]=Max(minp[i],pri[j]); 22 if(i%pri[j]==0) break; 23 } 24 } 25 } 26 namespace io { 27 const int SIZE = (1 << 21) + 1; 28 char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; 29 int f, qr; 30 #define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++) 31 inline void flush () {fwrite (obuf, 1, oS - obuf, stdout);oS = obuf;} 32 template <class I> 33 inline void fr (I &x) { 34 for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1; 35 for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); 36 x *= f; 37 } 38 struct Flusher_ {~Flusher_() {flush();}} io_flusher_; 39 } 40 using io :: fr; 41 il void fj(it x){ 42 while(x>1){ 43 it minn=minp[x],cnum=0; 44 while(minp[x]==minn&&x>1) x/=minp[x],++cnum; 45 if(cnum%k) g[pos].push_back(make_pair(minn,cnum%k)); 46 } 47 std::sort(g[pos].begin(),g[pos].end()); 48 } 49 int main(){ 50 fr(n),fr(k);prime(); 51 for(it i=1;i<=n;++i) fr(a[i]),pos=i,fj(a[i]); 52 for(it i=1;i<=n;++i){ 53 vec.clear(); 54 for(it j=0,sz=g[i].size();j<sz;++j) 55 vec.push_back(make_pair(g[i][j].first,(k-g[i][j].second)%k)); 56 ans+=mp[vec],++mp[g[i]]; 57 } 58 printf("%I64d",ans); 59 return 0; 60 }
E：暂时不会先咕着，等水平提升了补上
F：同E。
这次打的不好QAQ……下次继续努力啊！