- XJOI奮鬥群蒻蒟群群賽17 RANK排名9
-
- T1Increasing SequenceTLE一次AC
-
- 題意
- 分析過程
- 給出題解
-
- T2Jumping JackWA一次後AC
-
- 題意
- 分析過程
- 給出題解
-
- T3How Many Squares 已AC
-
- 題意
- 分析過程
- 給出題解
-
- T4A Simple TaskWA兩次之後AC
-
- 題意
- 分析過程
- 給出題解
-
- T5
-
- 題意
- 分析過程
- 給出題解
-
- T1Increasing SequenceTLE一次AC
-
—>XJOI奮鬥群（蒻蒟群）群賽17<— RANK排名9
T1：Increasing Sequence（TLE一次AC）
題意：
給你一個數列，然後給出你一個數d，數列中的每個數都可以加上d，問你最少加上幾次d，能夠使這個數列變成一個增序序列。
分析過程：
隻要每碰到一個數比前一個數小，就加上一定的值直到大于前一個數，最後輸出次數就行了。
給出題解：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,d;
int a[];
scanf("%d%d",&n,&d);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
long long cnt=;
for(int i=;i<=n;i++)
{
if(a[i]<=a[i-])
{
int dif=a[i-]-a[i];
dif/=d;
dif++;
a[i]+=d*dif;
cnt+=dif;
}
else continue;
}
printf("%d\n",cnt);
return ;
}
T2：Jumping Jack（WA一次後AC）
題意：
一個人在練習跳躍，第一次隻能跳一個機關，之後每一次跳就能夠比前一次長一個機關，問你經過多少次跳躍之後能夠準确地到達x這個位置。
分析過程：
由于x的值可能是正的也可能是負的，是以要先把x取絕對值。先預估sqrt（2*x）的值作為cnt的預估值，然後再從這個值開始向答案推進。
給出題解：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int x;
scanf("%d",&x);
x=abs(x);
int cnt=sqrt(*x);
while(cnt*(cnt+)/<x||(cnt*(cnt+)/-x)&)
cnt++;
printf("%d\n",cnt);
return ;
}
T3：How Many Squares? （已AC）
題意：
給你一個矩陣，問你其中有幾個正方形，要求正方形旁邊不能有多與的邊。
分析過程：
先便利每個數組中的
給出題解：
#include<bits/stdc++.h>
using namespace std;
int dic[][]= {{,},{,},{,-},{-,},{,},{,-},{-,},{-,-}};
char a[][];
int len=;
int n,m;
void judge(int x,int y)
{
if(x<||x>=n||y<||y>=m||a[x][y]!='1')return ;
a[x][y]='2';
len++;
for(int i=; i<; i++)
{
judge(x+dic[i][],y+dic[i][]);
}
}
bool solve(int x,int y,int len,int l,int r)
{
for(int i=; i<len+; i++)
for(int j=l; j<r; j++)
{
if(x+dic[j][]*i<||x+dic[j][]*i>=n||y+dic[j][]*i<||y+dic[j][]*i>=m||a[x+dic[j][]*i][y+dic[j][]*i]!='2')
return ;
}
return ;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=; i<n; i++)
scanf("%s",a[i]);
int res=;
for(int i=; i<n; i++)
for(int j=; j<m; j++)
{
if(a[i][j]=='1')
{
len=;
judge(i,j);
if(len%4)continue;
res+=solve(i,j,len/,,)&&solve(i+len/,j+len/,len/,,);
res+=solve(i,j,len/,,)&&solve(i+len/,j,len/,,);
}
}
printf("%d\n",res);
}
return ;
}
T4：A Simple Task（WA兩次之後AC）
題意：
給你一個簡單的無向圖，讓你統計其中環的個數。
分析過程：
我們設計一個狀态{[s][SET][i]}來記錄起點s到終點i的簡單路徑的條數，其中SET表示經過的節點的集合。但由于圓排列的性質，這樣的狀态是有重複的。我們通過指定起點為SET中的最小序号點來消除圓排列帶來的重複，狀态變為{[SET][i]}。還要注意，即使這樣定義狀态，計算簡單環個數的時候仍會将2個節點一條單邊的情況當成環，也會将長度大于2的環正向計算一遍，反向計算一遍。是以我們還要進行後處理。
前向的狀态轉移方程可以寫作：
dp[SET][j]=∑(i∈SET,i−j)dp[SET][i]
但這樣的方程并不利于統計簡單環的個數。
後向的狀态轉移方程可以寫作：
設簡單環的個數用統計量cnt表示。對于dp[SET][i]狀态，i的每一條邊eij,j∈neighbor(i)：若j∈SET則說明遇到了環，dp[SET][i]貢獻給cnt；若j∉SET則說明獲得一條簡單路徑，dp[SET][i]貢獻給dp[SET′][j]。
後處理：
由于長度為2的簡單環被統計了進去，是以cnt−m；又由于長度大于2的簡單環被統計了2遍，是以(cnt−m)/2。
最後要注意環的個數可能會達到19！個，是以我們需要用int64（之前被這個卡了好久）。
給出題解：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,ans,tot;
ll tmap[][],f[<<][];
ll get_p(int a)
{
for(int i=; i<n; i++)
{
if(a&(<<i)) return i;
}
}
ll solve()
{
ll i,j,k,p,s;
ans=;
tot=(<<n)-;
memset(f,,sizeof f);
for(i=; i<n; i++)
{
// printf("%d %d\n",1<<i,i);
f[<<i][i]=;
}
for(i=; i<=tot; i++)
{
for(j=; j<n; j++)
{
if(f[i][j]==) continue ;
p=get_p(i);
for(k=p; k<n; k++)
{
if(j==k) continue ;
if(tmap[j][k]==)continue;
if(i&(<<k))
{
if(k==p) ans+=f[i][j];
}
else
{
s=i|(<<k);
f[s][k]+=f[i][j];
}
}
}
}
ans-=m;
ans/=;
return ans;
}
int main()
{
scanf("%I64d%I64d",&n,&m);
memset(tmap,,sizeof tmap);
ll u,v;
for(int i=; i<=m; i++)
{
scanf("%I64d%I64d",&u,&v);
tmap[u-][v-]=tmap[v-][u-]=;
}
ll res=solve();
printf("%I64d\n",res);
return ;
}
}