zzuli第8回校試合問題解
一ヶ月も準備していた学校の試合はついに無駄にならず、チャンピオンになった...でも9題しか過ぎませんでした...文字列が下手なのでC問題はありません...
この問題は去年ほどよくなかったが,私は去年よくできなかっただろう.原題は3、4つ...
もう一つ難しい数論が出てこなかった....そういえば5分もかかって公式を出しました....最後の2時間は大丈夫だった...
A.シミュレーション
注意ピットの点は過程の中である値がintを爆発してそれから1つの0-255の数字をかき集めて、それから連続する2つの点です..
B.DP
lightojの原題は、n=1またはm=1が多くなった場合にのみ、特審すればよいのですが...lightoj無1題解接続:クリックして表示
C.文字列hash
二分の答えは文字列hashで判断できると思います.鳥神はmanacher+lcpという考えを提出しました.弱い準備は文字列をマスターして帰ってこの問題をします.
D.前処理+問合せ区間最小値
各点が何回上書きされるかを前処理してから、各セグメントについて列挙し、このセグメントの区間の最小値が何であるかを問い合わせることができます.2未満の場合、このセグメントのみが上書きされ、削除された後、他のセグメントは上書きされません.セグメントツリーが最適化されていないとカードされる可能性があります..変更されていないのでクエリーのみなので、私が採用したSTアルゴリズムは、nlognクエリーの複雑さを1として前処理しています...この問題に対する優位性は比較的大きい.
コード:
私は0年1月1日から2つの入力した日付がそれぞれ何日あるかを直接採用して、差を計算しました.これなら閏年について計算しやすいので、反発を許容することができます...閏年数はx/4-x/100+x/400...
F.数論
まず、gcdは減算に基づいて最適化されていることを明らかにします.では、この減算の過程は本当に最も素朴なgcdを求める過程に似ています.直接シミュレーションが爆発すると感じたので、サンプルをテストしてみました.
まずこの問題は一目でリュックサックに見え、リュックサックの体積と価値が大きすぎる.そこで,挑戦プログラム設計162ページの超大型リュックサック解の折半枚挙法を参照する.まずn個の品物を2つの山に分けて、それから各山のすべての状態を列挙して、最大2^15で、それから2つの山を満腹度で並べ替えます.最初は飽食度をキーワードにセグメントツリーを2つ目の山にしたいと思っていましたが、価格は無秩序な検索が煩わしいです.次に、追加操作やクエリーの最小値、指定値をサポートする場合は、setが最適であることは間違いありません.
第1の山については飽食度が小さいものから大きいものまで列挙し、この状態についてはkより大きいものとすべてsetを加えるという.これは列挙後の飽食度が大きい場合に第2の山に加わるこれらが肯定的に成立するため、setには最大2^15個の価格が加わる.
次に検索するときは、現在の最小価格を調べて、最初の価格と最小価格がxより大きいかどうかを見て、xより大きい場合は直接-yと現在の最小値を比較します.そうしない場合は、最初の価格+ある価格の値がxより大きい場合と最小の場合を選択します.そしてyを引いて答えと比較します.
弟はDFSを使って暴力を最適化してちょうど時間が過ぎた...
H.単純かつ調査セット
どれだけのルートがあるかを直接判断し、答えはルート数-1です.
I公式問題
身近なボスの重要性について
Jサイン
CF原題、1があれば必ずすべての数字を出すことができて、1がなければ1もできないのはきっとだめです..
この問題は去年ほどよくなかったが,私は去年よくできなかっただろう.原題は3、4つ...
もう一つ難しい数論が出てこなかった....そういえば5分もかかって公式を出しました....最後の2時間は大丈夫だった...
A.シミュレーション
注意ピットの点は過程の中である値がintを爆発してそれから1つの0-255の数字をかき集めて、それから連続する2つの点です..
B.DP
lightojの原題は、n=1またはm=1が多くなった場合にのみ、特審すればよいのですが...lightoj無1題解接続:クリックして表示
C.文字列hash
二分の答えは文字列hashで判断できると思います.鳥神はmanacher+lcpという考えを提出しました.弱い準備は文字列をマスターして帰ってこの問題をします.
D.前処理+問合せ区間最小値
各点が何回上書きされるかを前処理してから、各セグメントについて列挙し、このセグメントの区間の最小値が何であるかを問い合わせることができます.2未満の場合、このセグメントのみが上書きされ、削除された後、他のセグメントは上書きされません.セグメントツリーが最適化されていないとカードされる可能性があります..変更されていないのでクエリーのみなので、私が採用したSTアルゴリズムは、nlognクエリーの複雑さを1として前処理しています...この問題に対する優位性は比較的大きい.
コード:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int ja[120000],j[120000],l[120000],r[120000],x[120000];
int dp[120000][20],mm[120000];
int ans[120000];
void initrmq(int n,int b[])
{
mm[0]=-1;
for(int i=1;i<=n;i++)
{
mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
dp[i][0]=b[i];
}
for(int j=1;j<=mm[n];j++)
for(int i=1;i+(1<<j)-1<=n;i++)
dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int rmq(int x,int y)
{
int k=mm[y-x+1];
return min(dp[x][k],dp[y-(1<<k)+1][k]);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(ja,0,sizeof(ja));
memset(j,0,sizeof(j));
memset(x,0,sizeof(x));
memset(dp,0,sizeof(dp));
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d %d",&l[i],&r[i]);
ja[l[i]]++;
j[r[i]]++;
}
int tmp=0;
for(int i=1;i<=n;i++)
{
tmp+=ja[i];
x[i]+=tmp;
tmp-=j[i];
}
initrmq(n,x);
int cnt=0;
for(int i=1;i<=m;i++)
{
int tmp=rmq(l[i],r[i]);
if(tmp<=1)
continue;
else
ans[cnt++]=i;
}
printf("%d
",cnt);
for(int i=0;i<cnt;i++)
{
if(i==cnt-1)
printf("%d
",ans[i]);
else
printf("%d ",ans[i]);
}
}
return 0;
}私は0年1月1日から2つの入力した日付がそれぞれ何日あるかを直接採用して、差を計算しました.これなら閏年について計算しやすいので、反発を許容することができます...閏年数はx/4-x/100+x/400...
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int pd(int y)
{
if(y%400==0) return 1;
if(y%4==0&&y%100!=0) return 1;
return 0;
}
int mf[13]= {0,31,28,31,30,31,30,31,31,30,31,30,31};
int mr[13]= {0,31,29,31,30,31,30,31,31,30,31,30,31};
ll js(int y,int m,int d)
{
ll tmp=(y-1)/4-(y-1)/100+(y-1)/400;
tmp+=(y-1)*365;
for(int i=1;i<m;i++)
{
if(i==2&&pd(y))
tmp++;
tmp+=mf[i];
}
tmp+=d;
return tmp;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int y1,m1,d1,y2,m2,d2;
scanf("%d %d %d %d %d %d",&y1,&m1,&d1,&y2,&m2,&d2);
ll ans=js(y1,m1,d1);
ll tmp=js(y2,m2,d2);
ans=tmp-ans;
printf("%lld
",ans);
}
return 0;
}F.数論
まず、gcdは減算に基づいて最適化されていることを明らかにします.では、この減算の過程は本当に最も素朴なgcdを求める過程に似ています.直接シミュレーションが爆発すると感じたので、サンプルをテストしてみました.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define PI acos(-1.0)
int a[1200];
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
int ans=a[1];
int sum=a[1];
for(int i=2;i<=n;i++)
{
ans=gcd(ans,a[i]);
sum+=a[i];
}
printf("%d
",sum/ans);
}
return 0;
}まずこの問題は一目でリュックサックに見え、リュックサックの体積と価値が大きすぎる.そこで,挑戦プログラム設計162ページの超大型リュックサック解の折半枚挙法を参照する.まずn個の品物を2つの山に分けて、それから各山のすべての状態を列挙して、最大2^15で、それから2つの山を満腹度で並べ替えます.最初は飽食度をキーワードにセグメントツリーを2つ目の山にしたいと思っていましたが、価格は無秩序な検索が煩わしいです.次に、追加操作やクエリーの最小値、指定値をサポートする場合は、setが最適であることは間違いありません.
第1の山については飽食度が小さいものから大きいものまで列挙し、この状態についてはkより大きいものとすべてsetを加えるという.これは列挙後の飽食度が大きい場合に第2の山に加わるこれらが肯定的に成立するため、setには最大2^15個の価格が加わる.
次に検索するときは、現在の最小価格を調べて、最初の価格と最小価格がxより大きいかどうかを見て、xより大きい場合は直接-yと現在の最小値を比較します.そうしない場合は、最初の価格+ある価格の値がxより大きい場合と最小の場合を選択します.そしてyを引いて答えと比較します.
弟はDFSを使って暴力を最適化してちょうど時間が過ぎた...
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node
{
ll p,b;
} s1[80000],s2[80000];
ll p[50],b[50];
set<ll> s;
set<ll>::iterator it;
int cmp(node a,node b)
{
return a.b<b.b;
}
int main()
{
int t;
ll n;
ll k,x,y;
scanf("%d",&t);
while(t--)
{
cin>>n>>k>>x>>y;
ll sum=0;
for(int i=0; i<n; i++)
{
cin>>p[i]>>b[i];
sum+=b[i];
}
if(sum<k)
{
puts("go die");
continue;
}
s.clear();
int cnt1=0;
int tn=n/2;
for(int i=0; i<(1<<tn); i++)
{
ll tmpp=0,tmpb=0;
for(int j=0; j<tn; j++)
{
if(i&(1<<j))
{
tmpp+=p[j];
tmpb+=b[j];
}
}
s1[cnt1].p=tmpp;
s1[cnt1].b=tmpb;
cnt1++;
}
int nt=n-tn;
int cnt2=0;
for(int i=0; i<(1<<nt); i++)
{
ll tmpp=0,tmpb=0;
for(int j=0; j<nt; j++)
{
if(i&(1<<j))
{
tmpp+=p[j+tn];
tmpb+=b[j+tn];
}
}
s2[cnt2].p=tmpp;
s2[cnt2].b=tmpb;
cnt2++;
}
sort(s1,s1+cnt1,cmp);
sort(s2,s2+cnt2,cmp);
int j=cnt2-1;
ll ans=10000000000LL;
ll ax;
for(int i=0; i<cnt1; i++)
{
ll tmp=max(0LL,k-s1[i].b);
while(s2[j].b>=tmp&&j>=0)
{
s.insert(s2[j].p);
j--;
}
if(s.empty())
continue;
ax=s1[i].p;
if(ax+(*s.begin())<x)
{
ans=min(ans,ax+(*s.begin()));
ll c=max(0LL,x-ax);
it=s.lower_bound(c);
if(it==s.end())
continue;
ax+=(*it);
ax-=y;
ans=min(ans,ax);
}
else
ans=min(ans,ax+(*s.begin())-y);
}
cout<<ans<<endl;
}
return 0;
}H.単純かつ調査セット
どれだけのルートがあるかを直接判断し、答えはルート数-1です.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define PI acos(-1.0)
int f[2000];
void db(int n)
{
for(int i=1;i<=n;i++)
f[i]=i;
}
int finde(int x)
{
if(f[x]!=x)
return f[x]=finde(f[x]);
return x;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d %d",&n,&m);
db(n);
int u,v;
for(int i=0;i<m;i++)
{
scanf("%d %d",&u,&v);
int x=finde(u);
int y=finde(v);
if(x!=y)
f[x]=y;
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(f[i]==i)
ans++;
}
printf("%d
",ans-1);
}
return 0;
}I公式問題
身近なボスの重要性について
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define PI acos(-1.0)
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,a,l;
scanf("%d %d %d",&n,&a,&l);
double ans=a*a*n/4.0/tan(PI/n);
int cnt=0;
while(ans>l)
{
ans=ans*(cos(PI/n)*cos(PI/n));
cnt++;
}
printf("%d
",cnt);
}
return 0;
}Jサイン
CF原題、1があれば必ずすべての数字を出すことができて、1がなければ1もできないのはきっとだめです..