Current Server Time : 2021-08-12 17:17:29
Solved Pro.ID Title Ratio(Accepted / Submitted)
1001 X-liked Counting 15.15%(35/231)
1002 Buying Snacks 33.18%(70/211)
1003 Ink on paper 19.94%(743/3727)（生成樹，或二分答案建圖+并查集聯通性）
1004 Counting Stars 16.76%(299/1784)（線段樹，區間加，乘，標記）
1005 Separated Number 31.65%(138/436)
1006 GCD Game 20.05%(730/3640) (博弈論，nim游戲， 線性篩，質因子個數)
1007 A Simple Problem 0.00%(0/28)
1008 Square Card 22.40%(353/1576)（計算幾何，兩圓相交面積）
1009 Singing Superstar 28.63%(635/2218)（字串，AC自動機）
1010 Yinyang 12.73%(7/55)
1003 Ink on paper
題意：
- 給出平面中的n個點，每個點每秒向外擴散0.5cm，求多少時間后所有點的點會連在一起，輸出時間的平方，
思路：
- 其實是很簡單的最小生成樹板子，Kruskal或Prim都行大概O(nlogn)，但是比賽的時候沒想到，
- 然后寫了個二分答案，二分時間的平方，每次n^2列舉所有的點對建圖，并查集維護聯通性check時間是否可行，復雜度大概O(n^2logn)，防止超時可以提前預處理出所有點對之間的距離，避免每次重新算一遍，
- 開始用 double 二分的，精度一直WA，后來直接long long 二分時間的平方就過了，
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5050;
int fa[maxn+10];
void init(int n){for(int i = 1; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}
LL n, d[maxn][maxn];
struct node{LL x, y; }a[maxn];
LL getd(node x, node y){return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);}
bool check(LL t){
init(n);
int cnt = 1;
for(int i = 1; i <= n; i++){
for(int j = i+1; j <= n; j++){
if(t>=d[i][j]){
if(find(i)!=find(j)){
cnt++;
if(cnt==n)break;
merge(i,j);
}
}
}
if(cnt==n)break;
}
return cnt==n;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T; cin>>T;
while(T--){
cin>>n;
for(int i = 1; i <= n; i++)
cin>>a[i].x>>a[i].y;
for(int i = 1; i <= n; i++)
for(int j = i+1; j <= n; j++)
d[i][j] = getd(a[i],a[j]);
LL l = 0, r = 1e15+10;
while(l < r){
LL mid = (l+r)/2;
if(check(mid))r = mid;
else l = mid+1;
}
cout<<r<<"\n";
}
return 0;
}
1004 Counting Stars
題意：
- 給出一個長為n的序列（1e5），支持3種操作：
1：查詢[l,r]的區間和
2：修改[l,r]中每個數，都減去lowbit(x)
3：修改[l,r]中每個數，都加上2^k, 2^k<=ai
思路：
- 對于操作2，減去lowbit(x)相當于去掉最后一位的1，可以發現，不斷刪1后，一個數最多刪32次就會變為0，此后修改查詢都是0，所以我們可以打個tag表示該區間是否所有數為0，用標記下傳維護，剩余的情況暴力修改，
- 對于操作3，加上2^k相當于第一位1左移一位，可以發現，該操作僅與最高位有關，與后面的位無關，所以我們可以把最高位單獨維護，操作3相當于整個區間乘2，線段樹維護區間乘法即可，
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
const LL mod = 998244353;
LL a1[maxn], a2[maxn];
LL lowbit(LL x){ return x&(-x);}
//線段樹：s1維護最高位, s2維護剩余位，tg1表示區間乘2，tg2表示區間全為0，
LL s1[maxn<<2], s2[maxn<<2], tg1[maxn<<2], tg2[maxn<<2];
#define lch p<<1
#define rch p<<1|1
void pushup(int p){ //更新完pushup
s1[p] = (s1[lch]+s1[rch])%mod; //維護區間和
s2[p] = (s2[lch]+s2[rch])%mod; //維護區間和
tg2[p] = tg2[lch]&tg2[rch]; //左右子樹都全為0了才為0
}
void pushdown(int p){ //查詢前pushdown
tg1[lch] = tg1[lch]*tg1[p]%mod;
tg1[rch] = tg1[rch]*tg1[p]%mod;
s1[lch] = s1[lch]*tg1[p]%mod;
s1[rch] = s1[rch]*tg1[p]%mod;
tg1[p] = 1;
tg2[lch] |= tg2[p];
tg2[rch] |= tg2[p];
if(tg2[lch])s2[lch] = 0;
if(tg2[rch])s2[rch] = 0;
}
void build(int p, int l, int r){
tg1[p] = 1, tg2[p] = 0; //區間乘標記1,全為0標記0，
if(l == r){
s1[p] = a1[l], s2[p] = a2[l];
return ;
}
int mid = l+r>>1;
build(lch, l, mid);
build(rch, mid+1, r);
pushup(p);
}
LL query(int p, int l, int r, int ll, int rr){//return sum{s1+s2}[ll,rr];
if(ll>r || rr<l)return 0;
if(ll<=l && r<=rr){
return (s1[p]+s2[p])%mod;
}
pushdown(p);
int mid = l+r>>1;
LL ans = 0;
ans += query(lch, l, mid, ll, rr);
ans += query(rch, mid+1, r, ll, rr);
ans %=mod;
return ans;
}
void update1(int p, int l, int r, int ll, int rr){//s2[ll,rr]-=lowbit;(暴力)
if(ll>r || rr<l)return ;//區間在范圍外
if(tg2[p])return ; //區間全為0，再見
if(l==r){ //到葉節點才能單點暴力修改
if(s2[p]!=0){ s2[p]-=lowbit(s2[p]);}//去掉一個lowbit
else {s1[p]=0; tg2[p]=1;}//除了最高位已經都是0了，那最高位沒了
return ;
}
pushdown(p);
int mid = l+r>>1;
update1(lch, l, mid, ll, rr);
update1(rch, mid+1, r, ll, rr);
pushup(p);
}
void update2(int p, int l, int r, int ll, int rr){//s1[ll,rr] *= 2;(Lazy)
if(ll>r || rr<l)return ; //區間完全在范圍外
if(ll<=l && r<=rr){ //區間完全被包含
s1[p] = s1[p]*2%mod; //sum[l,r] *= 2;
tg1[p] = tg1[p]*2%mod; //lazy tag, then return ;
return ;
}
pushdown(p);
int mid = l+r>>1;
update2(lch, l, mid, ll, rr);
update2(rch, mid+1, r, ll, rr);
pushup(p);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T; cin>>T;
while(T--){
int n; cin>>n;
for(int i = 1; i <= n; i++){
LL x; cin>>x;
for(int k=30; k>=0; k--){
if((1ll<<k)<=x){ //找到最高位
a1[i] = 1ll<<k; //提取最高位
a2[i] = x-a1[i];//存剩余的數
break;
}
}
}
build(1,1,n);
int q; cin>>q;
for(int i = 1; i <= q; i++){
int op, l, r; cin>>op>>l>>r;
if(op==1)cout<<query(1,1,n,l,r)<<"\n";
else if(op==2)update1(1,1,n,l,r);
else update2(1,1,n,l,r);
}
}
return 0;
}
1006 GCD Game
題意：
- 給出n個數字ai，A和B輪流操作，每次任意選一個數ai，用任意x（1<=x<ai）計算gcd(ai, x)替換ai，不能操作時為輸，求誰能贏，
思路：
- nim游戲，把每個數看成一堆石子，石子個數就是每個數的質因子個數，提前用線性篩預處理一下10^7以內的質因子個數就行了，然后每次按照這個取數即可，
- （質因數：gcd(ai,x)一定是ai的因數，相當于每次取走ai一個因數，所有因數都可以被分解成質因數，即有多少個質因數相當于這一堆石頭有多少個石子，
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e7+10;
int num[maxn];//num[i]維護i的質因子個數
//線性篩
int vis[maxn], primes[maxn], cnt;
void get_primes(int n){
vis[0]=vis[1]=1;
for(int i = 2; i < n; i++){
if(!vis[i])primes[++cnt]=i, num[i]=1;
for(int j = 1; primes[j] <= n/i; j++){
vis[primes[j]*i] = 1;
num[primes[j]*i] = num[i]+1;
if(i%primes[j]==0)break;
}
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
get_primes(maxn-10);
int T; cin>>T;
while(T--){
int n; cin>>n;
int ans = 0;
for(int i = 1; i <= n; i++){
int x; cin>>x; ans ^= num[x];
}
if(ans!=0)cout<<"Alice\n";
else cout<<"Bob\n";
}
return 0;
}
1008 Square Card
題意：
- 給出兩個圓，分別代表得磁區域和獎勵區域，邊長為a的正方形卡片以均等概率扔到平面后繞得磁區域的圓心旋轉，
- 如果某一刻卡片完整的落在得磁區域或獎勵區域內，它將獲得相應的分數，求卡片同時獲得獎勵和得分的概率 比 卡片單獨獲得得分的概率 的比率，
思路：
- 可以發現，要使正方形卡片有可能被一個圓完全包含，它的中心軌跡一定是一個圓，所以本題就轉化為了計算兩圓相交面積與第一個圓面積的比值，
- 一些細節：如資料中獎勵區域不一定能完全包含卡片的不同情況要加特判，
- printf和cin一起用，關了流同步會WA，
#include<bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
//求兩圓相交面積
struct point{int x, y;};
double area(point a, double r1, point b, double r2){
double d = sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
if(d >= r1+r2)return 0;
if(r1 > r2)swap(r1,r2);
if(r2-r1>=d)return pi*r1*r1;
double ang1 = acos((r1*r1+d*d-r2*r2)/(2*r1*d));
double ang2 = acos((r2*r2+d*d-r1*r1)/(2*r2*d));
return ang1*r1*r1 + ang2*r2*r2 - r1*d*sin(ang1);
}
int main(){
int T; cin>>T;
while(T--){
double ra,xa,ya,rb,xb,yb,aa;
cin>>ra>>xa>>ya>>rb>>xb>>yb>>aa;
if(rb*rb-aa*aa/4<0){cout<<"0.000000\n"; continue;}
point a = point{(int)xa,(int)ya}, b = point{(int)xb,(int)yb};
double r1 = sqrt(ra*ra-aa*aa/4)-aa/2, r2 = sqrt(rb*rb-aa*aa/4)-aa/2;
double res = area(a, r1, b, r2);
printf("%.6f\n", res/(pi*r1*r1));
}
return 0;
}
1009 Singing Superstar
題意：
- 給出一個長度小于1e5的字串s，q<1e5次詢問，每次問一個長小于30的串t在s中的出現次數，t不可重疊，
思路：
- 開始寫了個回圈n遍kmp TLE了，算了一下復雜度大概O((|s|+30)*q)，肯定超時，然后寫了個字典樹將原先字串s每隔30個字母插入字典樹詢問，但是這樣獲得的結果是t可以重疊時的答案，
- 最后想到kmp+字典樹不如直接上自動機，找了一下ZOJ3228的板子改了一下，過了，對于允許重疊的情況，就是裸的AC自動機，不允許重疊的只需要：記錄trie樹上每個結尾節點一次匹配是在長串的哪個位置，若這次與上次不重疊則記錄，
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
struct node{ int type, index; char s[30];}a[maxn];
struct AC{
int num,ch[6*maxn][30],f[6*maxn],last[6*maxn],val[6*maxn];
int times[6*maxn][2],dep[7*maxn],pos[6*maxn];
void init(){
num=0;
memset(ch,0,sizeof(ch));
memset(f,0,sizeof(f));
memset(last,0,sizeof(last));
memset(val,0,sizeof(val));
memset(times,0,sizeof(times));
memset(dep,0,sizeof(dep));
memset(pos,-1,sizeof(pos));
return;
}
void insert(char *s,int qN){
int u=0,len=strlen(s),id;
for(int i=0;i<len;i++){
id=s[i]-'a';
if(!ch[u][id])ch[u][id]=++num;
u=ch[u][id];
}
val[u]=1;
dep[u]=len;
a[qN].index=u;
return;
}
void getfail(){
queue<int> Q;
Q.push(0);
int x,u,v;
while(!Q.empty()){
x=Q.front();Q.pop();
for(int i=0;i<26;i++){
u=ch[x][i];
if(!u){
ch[x][i]=ch[f[x]][i];
continue;
}
Q.push(u);
if(x==0) continue;
v=f[x];
while(v&&!ch[v][i]) v=f[v];
f[u]=ch[v][i];
last[u]=val[f[u]]?f[u]:last[f[u]];
}
}
return;
}
void find(char *s){
memset(times,0,sizeof(times));
int len=strlen(s),u=0,id,j;
for(int i=0;i<len;i++){
id=s[i]-'a';
u=ch[u][id];
j=u;
do{
times[j][0]++;
if(i-pos[j]>=dep[j]){
times[j][1]++;
pos[j]=i;
}
j=last[j];
}while(j);
}
return;
}
}ac;
int main(){
int T; cin>>T;
while(T--){
char s[maxn]; scanf("%s", s);
ac.init();
int q; cin>>q;
for(int i = 1; i <= q; i++){
scanf("%s", a[i].s);
a[i].type = 1; //不可重疊
ac.insert(a[i].s, i);
}
ac.getfail();
ac.find(s);
for(int i = 1; i <= q; i++){
if(a[i].type==0)printf("%d\n",ac.times[a[i].index][0]);
else printf("%d\n",ac.times[a[i].index][1]);
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/293826.html
標籤：其他
上一篇：夢之光芒/黑客小游戲
下一篇：Pygame制作跳躍小球小游戲