AtCoder Beginner Contest 206(Sponsored by Panasonic)(E,F)
E(容斥,gcd)
这个题大意就是给出一个\(l\)和一个\(r\),寻找满足以下条件的一对数\((x,y)\)的数量
\(gcd(x,y)!=1\)
\(gcd!=x\)并且\(gcd!=y\)(从这一句我们可以知道\(x\)不可能被\(y\)整除)
那么我们可以设\(x\)是\(t\)的倍数,\(y\)是\(t\)的倍数,先保证\(gcd(x,y)\)不为\(1\),
对于\([l,r]\)这一个区间可以是\(t\)的倍数的最小的数是\(\frac{l-1}{t}\times t\),最大的那个倍数是\(\frac{r}{t}\times t\),所以我们可以很简单的求出这个区间是\(t\)的倍数的数量\(cnt\),然后我们要让\(gcd(x,y)\)是\(t\)不仅要都要是\(t\)的倍数(\(w^2\),两个都从里面选),还可能会有\(gcd\)是\(2t\)等的,所以我们要减去那些可能是其他\(t\)的倍数的\(gcd\)的情况,用\(f[t]\)表示\(gcd\)是\(t\)的一对数的数量,那么需要减去\(f[2t]\)等等
然后我们再考虑第二句话的要求,\(x\)和\(y\)之间不能存在整除的关系,那么我们手动减去那些整除的一些
对于此时的\(gcd\)为\(t\)时,假设\(x=t\),那么存在可以是\(x\)的倍数的数有\(\frac{r}{x}\)个,同样假如\(y\)为\(t\)时,同样也是这么多,但是当\((t,t)\)只有一个,这里多计算了一次,需要减一
具体可以看代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const double eps=1e-9;
const int maxn=1e6+10;
const int mod=1e9+7;
int n;
int f[maxn],l,r;
signed main()
{
cin>>l>>r;
l--;
int ans=0;
for (int i=r;i>=2;i--)
{
int w=r/i-l/i;//(l-1)/i这个数最小的x*i>=l
f[i]=w*w;
for (int j=i+i;j<=r;j+=i)
{
f[i]-=f[j];
}
ans+=f[i];
}
for (int i=l+1;i<=r;i++)
{
if(i==1) continue;
int now=r/i;
now=now*2-1;
ans-=now;
}
cout<<ans<<"\n";
system ("pause");
return 0;
}
F(博弈,SG,记忆化)
这个题大意就是一个游戏,每个人都可以选择一个区间段,只要这一个区间没有和之前已经选过的区间重合即可,如果这个人选不出,那么这个人就输了
对于这一道题,就是用了\(sg\)函数和一些记忆化来写的
对于\(sg\)函数什么时候该用,什么时候不该用,我还不是很懂,之前也做过一次题,不过是通过打表得出规律的
感觉这个人的解释还蛮清楚的,学习
其中给出了一个公式
然后我们可以变化一下,得到
有了以上公式其他的都很好写了
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const double eps=1e-9;
const int maxn=100+10;
const int mod=1e9+7;
int n;
vector<int>g[maxn];
int dp[maxn][maxn];
int find(int l,int r)
{
if(l>r) return 0;
if(dp[l][r]!=-1) return dp[l][r];
set<int>st;
for (int ll=l;ll<=r;ll++)
{
for (auto rr:g[ll])
{
if(rr<=r)
{
int now=find(l,ll)^find(rr,r);
st.insert(now);
}
}
}
int now=0;
for (auto x:st)
{
if(now==x)
{
now++;
}
else
{
break;
}
}
dp[l][r]=now;
return dp[l][r];
}
void solve()
{
cin>>n;
for (int i=1;i<=100;i++)
{
g[i].clear();
}
memset(dp, -1, sizeof(dp));
for (int i=1;i<=n;i++)
{
int l,r;
cin>>l>>r;
g[l].push_back(r);
}
if(find(1,100)>0)
{
cout<<"Alice\n";
}
else
{
cout<<"Bob\n";
}
return ;
}
signed main()
{
int t;
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
- Sponsored Panasonic Beginner AtCoder Contestsponsored panasonic beginner atcoder sponsored beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 328