不是很理解为什么江西CSP单列一年,题目难度吊打CSP-J2024
签到题,但需要注意面积相等情况
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,c;
int main(){
cin >> a >> b >> c;
if(a*a>b*c){
cout << "Alice";
}else{
cout << "Bob";
}
return 0;
}
先考虑相似问题,若寻找最大值,则必然为严格次大数和最大数相模结果,猜测次大值也应该为较大数相模,玩了一会没找到很对的结论,于是直接把最大30个数字相模,取次大就过了
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
vector<int> a;
vector<int> ans;
map<int,bool> flag;
int n;
int main(){
cin >> n;
for(int i=1;i<=n;i++){
int x;
cin >> x;
if(!flag[x]) a.push_back(x);
else ans.push_back(0);
flag[x]=true;
}
sort(a.begin(),a.end());
for(int i=a.size()-1;i>=max(0,(int)a.size()-30);i--){
for(int j=0;j<a.size();j++){
if(i!=j) ans.push_back(a[j]%a[i]);
}
}
if(ans.size()==1){
cout << -1;
return 0;
}
sort(ans.begin(),ans.end());
//for(int i=0;i<ans.size();i++) cout << ans[i] << " ";
for(int i=ans.size()-2;i>=0;i--){
if(ans[i+1]!=ans[i]){
cout << ans[i];
return 0;
}
}
cout << -1;
return 0;
}
通过把玩小数据,发现最有解必然为$s1$,$s2$通过通过路径汇为一点,再从一点到原点(可通过反证法证明)。考虑到对于每一段简单路径,所需时间即为经过道路数,于是从原点,$s1$,$s2$分别跑一遍$dfs$,枚举汇集点即可,复杂度$O(n)$
#include<bits/stdc++.h>
using namespace std;
const int maxn=3005;
struct Node{
int x,t;
};
vector<int> e[maxn];
int Tim[maxn],T1[maxn],T2[maxn],n,m;
int s1,t1,s2,t2;
bool Visit[maxn];
queue<Node> q;
void dfs1(){
q.push((Node){1,0});
Visit[1]=1;
while(q.size()){
int x=q.front().x;
int t=q.front().t;
q.pop();
Tim[x]=t;
for(int i=0;i<e[x].size();i++){
int to=e[x][i];
if(Visit[to]) continue;
Visit[to]=true;
q.push((Node){to,t+1});
}
}
}
void dfs2(){
memset(Visit,0,sizeof(Visit));
q.push((Node){s1,0});
Visit[s1]=1;
while(q.size()){
int x=q.front().x;
int t=q.front().t;
q.pop();
T1[x]=t;
for(int i=0;i<e[x].size();i++){
int to=e[x][i];
if(Visit[to]) continue;
Visit[to]=true;
q.push((Node){to,t+1});
}
}
}
void dfs3(){
memset(Visit,0,sizeof(Visit));
q.push((Node){s2,0});
Visit[s2]=1;
while(q.size()){
int x=q.front().x;
int t=q.front().t;
q.pop();
T2[x]=t;
for(int i=0;i<e[x].size();i++){
int to=e[x][i];
if(Visit[to]) continue;
Visit[to]=true;
q.push((Node){to,t+1});
}
}
}
int main(){
// freopen("P5683.in","r",stdin);
cin >> n >> m;
for(int i=1;i<=n;i++){
Tim[i]=T1[i]=T2[i]=maxn*2;
}
for(int i=1;i<=m;i++){
int x,y;
cin >> x >> y;
e[x].push_back(y);
e[y].push_back(x);
}
cin >> s1 >> t1 >> s2 >> t2;
dfs1();
dfs2();
dfs3();
int ans=-1;
for(int i=1;i<=n;i++){
// cout << T1[i] << " " << T2[i] << endl;
int tt1=Tim[i]+T1[i];
int tt2=Tim[i]+T2[i];
if(tt1>t1) continue;
if(tt2>t2) continue;
if(ans==-1){
ans=T1[i]+T2[i]+Tim[i];
}else{
ans=min(T1[i]+T2[i]+Tim[i],ans);
}
}
// cout << ans << " ";
if(ans==-1){
cout << -1;
}else{
cout << m-ans;
}
return 0;
}
发现正向构造非回文串较复杂,于是考虑先计算全排列数量,再减去回文情况。记得及时取模,以及乘法逆元的运用
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
const int maxn=2005;
ll n;
string s;
ll c[maxn];
ll f[maxn];
void init(){
f[0]=1;
for(int i=1;i<maxn;i++) f[i]=f[i-1]*i,f[i]%=MOD;
}
ll Pow(ll a,ll b){
ll Base=a;
ll Re=1;
while(b){
if(b&1){
Re*=Base;
Re%=MOD;
}
Base*=Base;
Base%=MOD;
b>>=1;
}
return Re;
}
int main(){
init();
cin >> n;
cin >> s;
for(int i=0;i<n;i++){
c[s[i]-'a'+1]++;
}
ll Base=f[n];
bool flag=!(n%2);
ll Dt=f[n/2];
for(int i=1;i<=26;i++){
if(c[i]%2==1){
if(flag){
cout << Base;
return 0;
}
flag=true;
}
Dt*=f[c[i]];
Dt%=MOD;
Dt*=Pow(f[c[i]/2],MOD-2);
Dt%=MOD;
}
cout << ((Base-Dt)%MOD+MOD)%MOD;
return 0;
}
标签:int,ll,VP,maxn,ans,J2019,CSP
From: https://www.cnblogs.com/Ding0023/p/18324290