這次做了ABDF。我也不知道我怎么做的（亂做-.-

A - Air Conditioner

簽到題1

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #define debug(x) cout<<#x<<": "<<x<<" " #include<iostream> #include<algorithm> using namespace std; int main() {IO;int T;cin>>T;if(T>=30) cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0; }

B - Distance

簽到題2

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #define debug(x) cout<<#x<<": "<<x<<" " #include<iostream> #include<algorithm> using namespace std; typedef long long ll; int main() {IO;int n;ll d;cin>>n>>d;int res=0;while(n--){ll x,y;cin>>x>>y;if(x*x+y*y<=d*d) res++;}cout<<res<<endl;return 0; }

C - Repsept

群里大佬說k是2或5的倍速顯然不行，其他再int范圍內顯然有解（為啥我看不出來顯然）。反正實在不行就暴力長度$1\dots 10^7$

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #include<iostream> #include<algorithm> using namespace std; typedef long long ll; int main() {IO;ll k;cin>>k;if(k%2==0||k%5==0){cout<<-1<<endl;return 0;}ll sum=0,len=1,p=1;while(true){sum=(sum+7*p)%k;if(sum==0) {cout<<len<<endl;break;}len++;p=p*10%k;}return 0; }

反思：好幾次看到這種大數的都想著高精度，而且每次看到題解的時候都是因為模了一個數最終避免高精度。下次想高精度的時候需要考慮下是否能過模一個數避免高精度

D - Alter Altar

最終R全在左邊，W全在右邊，按照快排時候的策略，貪心+雙指針。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #define debug(x) cout<<#x<<": "<<x<<" " #include<iostream> #include<algorithm> #include<string> using namespace std; typedef long long ll; int main() {IO;int n;string s;cin>>n>>s;int i=0,j=n-1;int res=0;while(i<j){if(s[i]=='R'&&s[j]=='W') i++,j--;else if(s[i]=='W'&&s[j]=='R') res++,i++,j--;else if(s[i]=='W'&&s[j]=='W') j--;else i++;}cout<<res<<endl;return 0; }

E - Logs

最大值最小二分答案。u1s1這個題不難。考試怎么沒做！！！wctl

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=200010; int a[N],n,k; bool check(int mid) {ll res=0;for(int i=1;i<=n;i++) res+=(a[i]+mid-1)/mid-1;return res<=k; } int main() {IO;cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];int l=1,r=1e9;while(l<r){int mid=l+r>>1;if(check(mid)) r=mid;else l=mid+1;}cout<<l<<endl;return 0; }

F - Range Set Query

HH的項鏈
解法一：莫隊板子題$5\times 10^5$過不了?那我開個O2還真讓我水過了（滑稽
$O(m\sqrt{n})$ 1953 ms

#pragma GCC optimize(2) #include<iostream> #include<algorithm> #include<cstdio> #include<cmath> using namespace std; typedef long long ll; const int N=500010; int pos[N],sz; int cnt[N]; int a[N]; int ans[N]; ll res; struct node {int l,r,k;bool operator <(const node& o)const{if(pos[l]==pos[o.l]) return r<o.r;return pos[l]<pos[o.l];} }q[N]; int n,m; void add(int k) {cnt[a[k]]++;if(cnt[a[k]]==1) res++; } void sub(int k) {cnt[a[k]]--;if(cnt[a[k]]==0) res--; } int main() {scanf("%d%d",&n,&m);sz=sqrt(n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);pos[i]=i/sz;}for(int i=0;i<m;i++){int l,r;scanf("%d%d",&l,&r);q[i]={l,r,i};}sort(q,q+m);int l=1,r=0;for(int i=0;i<m;i++){while(l<q[i].l) sub(l++);while(l>q[i].l) add(--l);while(r<q[i].r) add(++r);while(r>q[i].r) sub(r--);ans[q[i].k]=res;}for(int i=0;i<m;i++) printf("%lld\n",ans[i]);return 0; }

解法二：離線樹狀數組
對于求不同數的個數，給定區間一個數出現n次對答案的貢獻只是1，我們不妨讓每次貢獻都看作是該區間最后這個數的出現給予的（前面出現的不算答案的貢獻）。樹狀數組維護每個數對答案的貢獻。
$O(mlogn+n)$ 222 ms

#include<iostream> #include<algorithm> #include<cstdio> using namespace std; typedef long long ll; const int N=500010; int tree[N]; int a[N],last[N];//a[]原數組 last[x]動態記錄x再原數組最后一次出現的位置 int ans[N]; int n,m; struct node {int l,r,k;bool operator <(const node& o)const{return r<o.r;} }q[N]; int lowbit(int x) {return x&-x; } void add(int x,int c) {for(;x<=n;x+=lowbit(x)) tree[x]+=c; } int sum(int x) {int res=0;for(;x;x-=lowbit(x)) res+=tree[x];return res; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=0;i<m;i++){int l,r;scanf("%d%d",&l,&r);q[i]={l,r,i};}sort(q,q+m);//按照區間右端點排序int k=1;//指針 動態維護到的位置（每次維護到詢問右端點）for(int i=0;i<m;i++)//每一個詢問{for(;k<=q[i].r;k++){int x=a[k];if(last[x]) add(last[x],-1);//說明x之前出現過 在之前出現的位置減1add(k,1);//該位置產生了一個新種類的數last[x]=k;}ans[q[i].k]=sum(q[i].r)-sum(q[i].l-1);}for(int i=0;i<m;i++) printf("%lld\n",ans[i]);return 0; }

要加油哦~

總結

以上是生活随笔為你收集整理的AtCoder Beginner Contest 174 总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。