Forgetting Things

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 3e5+20; const int MOD = 1e9+7; int n; int main() { int a,b; cin >> a >> b; if(a==b){cout << a << "0" << " " << b << "1" << endl;} else if(a+1==b){cout << a << " " << b << endl;} else if(a==9 && b == 1)cout << "9 10" << endl; else puts("-1"); }

TV Subscriptions (Easy Version)

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2e5+20; const int MOD = 1e9+7; int n,k,d; map<int,int>ma; int num[MAXN]; int main() { int _; cin >> _; while (_--){ cin >> n >> k >> d; ma.clear(); int minn=d; for (int i = 0; i < n; ++i) { cin >> num[i]; ma[num[i]]++; if(i >= d){ ma[num[i-d]]--; if(ma[num[i-d]]==0){ ma.erase(num[i-d]); } } if(i>=d-1){ minn=min(minn,(int)ma.size()); } //cout << "i:" << i << ":size:" << ma.size() << endl; } cout << minn << endl; } }

TV Subscriptions (Hard Version)

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2e5+20; const int MOD = 1e9+7; int n,k,d; map<int,int>ma; int num[MAXN]; int main() { int _; cin >> _; while (_--){ cin >> n >> k >> d; ma.clear(); int minn=d; for (int i = 0; i < n; ++i) { cin >> num[i]; ma[num[i]]++; if(i >= d){ ma[num[i-d]]--; if(ma[num[i-d]]==0){ ma.erase(num[i-d]); } } if(i>=d-1){ minn=min(minn,(int)ma.size()); } //cout << "i:" << i << ":size:" << ma.size() << endl; } cout << minn << endl; } }

p-binary

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2e5+20; const int MOD = 1e9+7; ll n,k; int loglen(ll i){ int len=0; while(i){ i >>= 1; len++; //cout << i << endl; } return len; } int renum(ll i){ int len=0; while (i){ if(i&1)len++; i >>= 1; } return len; } int main() { cin >> n >> k; int lenn=loglen(n); int lenn2=loglen(n-lenn*k); for (int i = 0; i < 30; ++i) { n-=k; if(n<=0){ puts("-1"); return 0; } if(i+1>n && k>=0){ puts("-1");return 0; } int rn = renum(n); //cout << rn << "rn" << endl; if(rn <= i+1){ cout << i+1 << endl;return 0; } } puts("-1"); return 0; }

Power Products

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1e5+20; const int MOD = 1e9+7; #define coutdebug(i) {cout<<"(i)"<<(i)<<endl;} int n,k; ll num[MAXN]; map<int,ll>ma,mf; vector<int>vec; ll cpow(ll i,int b=k){ if(b==0)return 1; ll ans = i; if(i==1)return i; for (int j = 1; j < b; ++j) { ans*=i; if(ans > 1e10)return -1; } return ans; } ll fun(ll a, int b=k ) { ll r = 1; ll base = a; while( b) { if(b & 1){ r *= base; if(r > 1e10)return -1; if(b==1)return r; } base *= base; //注意：a^{2^7}=a^{2^6} * a^{2^6} ，而不是 a^{2^7}=a^{2^6} * a ，所以这是对的。 if(base > 1e10)return -1; b /= 2;//与b=b>>1相同 } return r; } int factor(int n) { int remain=1; for(int i=2,a=1; i*i<=n; i+=a,a=2) { int cnt=0; if(n%i==0) while(n%i==0) { cnt++; n /= i; } remain*=cpow(i,cnt%k); } if(n > 1) remain*=n; return remain; } int main() { scanf("%d%d",&n,&k); ll min0=MAXN,max0=0; ll max1,min1; for (int i = 0; i < n; ++i) { int cur; scanf("%d",&cur); cur=factor(cur); //cout << cur << endl; num[cur]++; ma[cur]++; max0=max(max0,(ll)cur); min0=min(min0,(ll)cur); } if(k==2){ ll ans=0; for (int i = 1; i <= max0; ++i) { if(num[i]) ans+=num[i]*(num[i]-1)/2; } cout << ans << endl; return 0; } { auto it = ma.end(); it--; max0=it->first; if(it->second==1){ it--; max1=it->first; } else max1=it->first; auto it1=ma.begin(); min0=it1->first; if(it1->second==1){ it1++; min1=it1->first; } else min1=it1->first; } for (auto mit=ma.begin();mit!=ma.end();mit++) vec.push_back(mit->first); ll ans=0; for (ll i = 1;i<=max0; ++i) { //cout << "i:" << i << endl; ll powk=fun(i); if(powk==-1)break; if(powk<min0*min1)continue; if(powk>max0*max1)break; auto it = std::lower_bound (vec.begin(), vec.end(), (powk/max0)); //cout << "lowerbound:" << it->first << endl; for (; it!=vec.end(); ++it){ ll a=(*it); if(a*a>powk)break; if(powk%a!=0)continue; ll b=powk/a; if(b > max0)continue; //cout << a << " a b " << b << endl; if(a==b){ ans+=(num[a])*(num[a]-1)/2; break; } if (num[b]){ ans+=(num[a])*(num[b]); } } //cout << "ans" << ans << endl; } cout << ans << endl; } /* 2 1 1 1 9 2 2 4 6 8 10 11 11 12 16 8 2 2 4 6 8 10 11 11 12 */

Rock Is Push

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2e3+20; const ll MOD = 1e9+7; char s[MAXN][MAXN]; ll d[MAXN][MAXN]; ll d2[MAXN][MAXN][2]; ll sum[MAXN][MAXN][2]; int vertical[MAXN][MAXN],horizontal[MAXN][MAXN]; #define coutdebug(i) {cout<<"debug"<<(i)<<endl;} int n,m; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%s",s[i]+1); if(s[1][1]=='R'||s[n][m]=='R'){puts("0");return 0;} for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) vertical[i][j]=(vertical[i][j-1]+(s[n-j+1][i]=='R'?1:0)); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) {horizontal[i][j]=(horizontal[i][j-1]+(s[i][m-j+1]=='R'?1:0));} d[1][1]=d2[1][1][0]=d2[1][1][1]=sum[1][1][0]=sum[1][1][1]=1; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if(i == 1 && j == 1)continue; int a = m+1-j; int idx = lower_bound(horizontal[i]+1,horizontal[i]+m+1,a)-(horizontal[i]+1); int idx2=m-idx; if(idx2==j)d2[i][j][1]=0; else d2[i][j][1]=(d[i][j-1]-d[i][idx2]+d2[i][idx2][0]); //d2[i][j][1]=0; //for (int k = idx2; k <= j-1; ++k)d2[i][j][1]=(d2[i][j][1]+d2[i][k][0])%MOD; d2[i][j][1]=(sum[i][j-1][0]-sum[i][min(idx2-1,j-1)][0]+MOD)%MOD; int b=n+1-i; idx = lower_bound(vertical[j]+1,vertical[j]+n+1,b)-(vertical[j]+1); int idx3=n-idx; if(idx3==i)d2[i][j][0]=0; else d2[i][j][0]=(d[i-1][j]-d[idx3][j]+d2[idx3][j][1]); //d2[i][j][0]=0; //for (int k = idx3; k <= i-1; ++k)d2[i][j][0]=(d2[i][j][0]+d2[k][j][1])%MOD; d2[i][j][0]=(sum[i-1][j][1]-sum[min(idx3-1,i-1)][j][1]+MOD)%MOD; sum[i][j][1]=(d2[i][j][1]+sum[i-1][j][1])%MOD; sum[i][j][0]=(d2[i][j][0]+sum[i][j-1][0])%MOD; d[i][j]=(d2[i][j][0]+d2[i][j][1])%MOD; // cout << i << " i j " << j << endl; // cout << "idx2 " << idx2 << endl; // cout << "idx3 " << idx3 << endl; // cout << "d[i][j] " << d[i][j] << endl; // cout << "d[i][j][0] " << d2[i][j][0] << endl; // cout << "d[i][j][1] " << d2[i][j][1] << endl; // cout << "sum[i][j][1] " << sum[i][j][1] << endl; // cout << "sum[i][j][0] " << sum[i][j][0] << endl; } } cout << (d[n][m])%MOD << endl; } /* 5 2 .. .R .. .R .. 5 3 ... .R. ... .R. ... 2 3 ... .R. 2 3 .R. .R. 2 3 .R. R.. 5 3 ... .R. R.R .R. ... 2 2 .. R. 3 2 .. R. .. 2 4 .R.. .R.. 3 4 .... .RR. .... */

Tree Factory

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1e5+20; const ll MOD = 1e9+7; #define coutdebug(i) {cout<<"debug"<<(i)<<endl;} struct Node{ int v,d; bool operator <(Node n){ return d > n.d; } }; vector<Node>vec[MAXN]; vector<int>num,cut; int n; int depth(int u){ if(vec[u].size()==0)return 0; int maxn=0; for (auto &c : vec[u]) { c.d = depth(c.v);; maxn=max(maxn,c.d); } return maxn+1; } void dfs(int u,int app){ if(app>=0)cut.push_back(app); for (int i = 0;i < vec[u].size();i++) { int v = vec[u][i].v; //cout << u << " u v " << v << endl; //cout << " d " << vec[u][i].d << endl; if(!i)dfs(v,app); else dfs(v,vec[u][i-1].v); } num.push_back(u); } int main() { scanf("%d",&n); for (int i = 1; i < n; ++i) { int cur;scanf("%d",&cur); vec[cur].push_back(Node{i,0}); } depth(0); for (int i = 0; i < n; ++i) sort(vec[i].begin(),vec[i].end()); dfs(0,-1); for (int i = 0; i < n; ++i)printf("%d ",num[n-i-1]); //for (int i = 0; i < n; ++i)printf("%d ",num[i]); puts(""); cout << cut.size() << endl; for (int i = cut.size()-1; i >= 0; --i) printf("%d ",cut[i]); } /* 6 0 0 1 3 2 10 0 1 1 3 0 5 6 7 7 */