比赛链接杭电多校第二场-hduoj
这次过了五题，又又又又绝杀了...这回时间是04:59:49，原因是1003数据太过简单，暴力就可以，zyx最后11s交上AC。
总体来说一开始的两个数学题有点炸心态（1012,1009)，队伍排名有所下降，上一次是164，要不定一个目标吧，就定在前300。补题有1001还打算补1011，最近太累了，先更新部分的，还是按题目顺序来。
1002.C++ to Python（签到）
这个题我第一反应是这个CF190C - Codeforces，自信的接下了这个题，但是没想到这个这么简单...我以为可以像cf这个题去用递归...实际上只需要for循环判断，输出想要的即可。
可以再看看这个CF190C:题意通过输入的pair和int来最后输出总的类型，例如：
Input:
3
pair pair int int int
Output:
pair<pair<int,int>,int>
可以用递归来，如果是pair则在递归前加上<,>这类即可。十分巧妙。
void dfs()
{
if(cin >> s)
{
ans+=s;
if(s=="pair")
{
ans+="<";
dfs();
ans+=",";
dfs();
ans+=">";
}
} else ok=1;
}
本题代码也十分简单：
inline void Case_Test()
{
cin>>s;
n=s.size();
for (int i=0;i<n;i++)
{
if (s[i]>='0'&&s[i]<='9')//我写[1,9]wa了一发...罪犯
cout<<s[i];
else if (s[i]=='('||s[i]==')'||s[i]==','||s[i]=='-')
cout<<s[i];
}
cout<<endl;
}
1007.Snatch Groceries（贪心,签到）
阅读理解题，题面很长
题意：给你若干个区间，从时间小的开始安排任务，如果在某个时间点有冲突则表示不能继续下去，求冲突前最多能够有多少个任务可以完成。
思路：按区间的左端点排序，然后每次用下一个的左端点比较当前的右端点，如果可以则计数，否则break
代码：
struct node
{
int l,r;
}a[N];
inline void Case_Test()
{
cin>>n;
for (int i=1;i<=n;i++)
cin>>a[i].l>>a[i].r;
sort(a+1,a+1+n,[](node a,node b){return a.l<b.l;});
int ans = 0;
a[n+1].l = inf;
for (int i=2;i<=n+1;i++)
{
if (a[i].l>a[i-1].r) ans++;//计数
else break;//退出
}
cout<<ans<<endl;
}
1012.Luxury cruise ship（思维+背包）
题意：给出正整数$n(n\leq 10^{18})$，求正整数$x,y,z$满足方程$7x+31y+365z=n$的条件下，$(x+y+z)_{min}$
思路：这个题十分巧妙，收获很大。首先观察这三个互质，这是十分重要的，并且可以得出$lcm=7\times 31\times 365=79205$.
对于一个$n$首先分成两部分：
- 整除。为$lcm$的整数倍。对于一个$lcm$我们可以一直可以选择$365$去减少，一直选择$7\times 31$个$365$。这样保证了最小，又满足了达到$lcm$。
Question:会不会可以少选一个$365$，在$79205$的基础上加一个小的$x$是的其他用$7$或者$31$填满呢？
Answer:其实我这里写的“不会”但是越想越不对劲，因为实际上是可以的，例如我这里的$x=6$,现在我可以少减去一个$365$，在剩下的$365+6=371$里面每次减$7$（为$7$的倍数），所以是可以的...但是以我的程序是不可以的... - 余数。小于$lcm$的部分。
...继续写下去吧...小的部分就用完全背包，dp[i]表示能够选i的最小个数，例如dp[14]=2，dp[45]=dp[14+31]=3
那么如何解决这个问题，实际上像std一样预处理多一些就好了，我只预处理到了lcm=79205。所以这个hack数据79211应该输出245，但是我输出-1...小数据肯定在预处理范围内，大数据直接用上面方法用$365$减完就好。
代码：
int dp[N];
inline void init(int n)//n=lcm
{
for (int i=1;i<n;i++)
dp[i] = inf;
dp[0] = 0;
for (int i=1;i<n;i++)
{
if (i>=7) dp[i] = Min(dp[i],dp[i-7]+1);
if (i>=31) dp[i] = Min(dp[i],dp[i-31]+1);
if (i>=365) dp[i] = Min(dp[i],dp[i-365]+1);
}
}//预处理，应该预处理更多的
inline void Case_Test()
{
cin>>n;
ans = n/lcm*(7*31);
n%=lcm;
if (dp[n]!=inf) cout<<ans+dp[n]<<endl;
else cout<<-1<<endl;
}
1009.ShuanQ（数学，质因数分解）
题意：给你两个加密解密方式分别是：
$$
Encryption \space formula: \space E=R \times P \space mod \space M \ Decryption \space formula: \space R=E\times Q \space mod \space M
$$
现在已知$P,Q,E(P,Q,E\leq 2\times 10^6)$，并且$P\times Q \equiv 1 \space mod \space M$，并且$M$是质数。
思路：这个问题主要是不知道$m$的范围，我首先写了一发线筛，每次枚举$2e6$内的质数$m$，但是其实是要枚举$4e12$的...因为是$P\times Q$
通过$P\times Q \equiv 1 \space mod \space M$可以来推测$M$，可以得到存在一个$k$满足，$P\times Q-1=k\times M$（倍数关系），这里可以得到$kM$，那么题目中的质数$M$与其的关系是什么呢？这里的$M$是$kM$的一个质因子，并且一定要比$P,Q$要大。
因为是质因子，所以只需要对$M$质因数分解即可，$k$肯定不用管。
最多只有一个质因子满足要求，如果有多个满足要求$M_1,M_2$质因子，那么$kM=M_1\times M_2 \gt P\times Q$ 矛盾
然后枚举每次质数进行判断，是否满足上面两个式子即可，但是注意这里的取模要比$P,Q$要大，不然会wa。
代码：
vector<int> divide(int x)
{
vector<int> ans;
for (int i=2;i*i<=x;i++)
{
if (x%i==0)
{
ans.push_back(i);
while (x%i==0)
x/=i;
}
}
if (x>1)
ans.push_back(x);
return ans;
}//质因数分解，队友竟然还有不会写的！
inline void Case_Test()
{
cin>>p>>q>>e;
n = p*q-1;
vector<int> res = divide(n);
for (auto m:res)
{
if (e>=m||p>=m||q>=m) continue;//一定判p>=m,q>=m，m一定要大于他们俩
int r = e*q%m;
if (e==r*p%m)
{
cout<<r<<endl;
return;
}//满足条件
}
cout<<"shuanQ"<<endl;
}
文章评论