2022/9/22-2022/9/23

Source

C-Mean Streets of Gadgetzan_第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(沈阳) 构造

怎样构造其实很明显的能看出来,只要有->这种东西的,那么我左边只要有一个为假那么右边的值就可以随便取,那对于不确定的命题来说当然是尽量让他是假命题,然后实现却不大会了,最后还是看的题解,,,

代码查看 (nowcoder.com)

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define endl '\n'
#define lowbit(i) (i)&(-i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const ll mod=1e9+7;
const double inf=1e18;
const double eps=1e-8;
ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll getinv(ll a){return qpow(a,mod-2);}
ll lcm(ll a,ll b){
    return a*b/__gcd(a,b);
}
ll n,m,ri[1000006],ans[1000006],deg[1000006],vis[1000006];
vector<ll>id[1000006];
queue<ll>q;
string s;
void gg(){cout<<"conflict"<<endl;exit(0);}
int main(){
    //cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    cin>>n>>m;getchar();
    for(int i=1;i<=n;i++){
        getline(cin,s); 
        ll cnt=0,idx=s.find("->");
        if(idx!=-1){
            string tmp="";
            for(int j=0;j<idx;j++){
                if(s[j]==' '){
                    cnt++;
                    ll x=stoi(tmp);tmp="";
                    id[x].push_back(i);
                }
                else tmp+=s[j];
            }
            deg[i]=cnt;
            if(s[idx+3]=='!'){
                ll x=stoi(s.substr(idx+4));
                ri[i]=-x;
            }
            else{
                ll x=stoi(s.substr(idx+3));
                ri[i]=x;
            }
        }
        else{
            if(s[0]=='!'){
                ll x=stoi(s.substr(1));
                if(ans[x]==1) gg();
                ans[x]=-1;
            }
            else{
                ll x=stoi(s);
                if(ans[x]==-1) gg();
                ans[x]=1;
                q.push(x);
            }
        }
    }
    while(!q.empty()){
        ll x=q.front();q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(auto u:id[x]){
            deg[u]--;
            if(deg[u]<=0){
                if(ri[u]<0&&ans[-ri[u]]==1||ri[u]>0&&ans[ri[u]]==-1) gg();
                if(ri[u]>0){
                    ans[ri[u]]=1;
                    q.push(ri[u]);
                }
                else ans[-ri[u]]=-1;
            }
        }
    }
    for(int i=1;i<=m;i++)
    if(ans[i]==1) cout<<"T";
    else cout<<"F";
    system("pause");
    return 0;
}


Jason ABC 双指针

其实最多也就删两次,因为肯定是有一个字母出现的次数等于n的,所以遍历到这个字母出现了n次之后就可以把后边的字母都刷成其他两个字母就可以;

那么就可以讨论一下:

0次:每个字母都等于n

1次:只有一个字母的个数小于n,那么就双指针遍历一下找一段满足将这个区间全刷成这个字母可以满足条件区间[l,r]

2次:和一开始说的一样,遍历到这个字母出现了n次之后就可以把后边的字母都刷成其他两个字母就可以

较难的地方可能就是双指针的地方了,做这个题的时候脑子锈了啥也没想出来

2021 ICPC Southeastern Europe Regional Contest(更新至六题)_追随远方的某R的博客-CSDN博客

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define endl '\n'
#define lowbit(i) (i)&(-i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const ll mod=1e9+7;
const double inf=1e18;
const double eps=1e-8;
ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll getinv(ll a){return qpow(a,mod-2);}
ll lcm(ll a,ll b){
    return a*b/__gcd(a,b);
}
ll pri[1000006],cnt=0;
bool ispri[1000006];
void is_pri(ll n){
    memset(ispri,1,sizeof(ispri));
    ispri[0]=ispri[1]=0;
    for(int i=2;i<=n;i++){
        if(ispri[i]) pri[++cnt]=i;
        for(int j=1;j<=cnt&&i*pri[j]<=n;j++){
            ispri[i*pri[j]]=0;
            if(i%pri[j]==0) break;
        }
    }
}
ll a[1000006],b[1000006],ct=0,n;
vector<ll>v[1000006];
int main(){
    //cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    is_pri(1000000);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        for(int j=1;j<=cnt;j++){
            ll tmp=a[i];
            if(a[i]%pri[j]==0){
                if(v[pri[j]].size()==0) b[++ct]=pri[j];
                v[pri[j]].push_back(i);
                while(a[i]%pri[j]==0) a[i]/=pri[j];
            }
            if(ispri[a[i]]){
                if(v[a[i]].size()==0) b[++ct]=a[i];
                v[a[i]].push_back(i);
                break;
            }
            if(a[i]<=1) break;
        }
    }
    ll ans=0;
    for(int i=1;i<=ct;i++){
        ll x=b[i],y=0;
        for(int j=0;j<v[x].size();j++){
            ll k=v[x][j];
            ans+=(k-y)*(n-k+1);
            y=k;
        }
    }
    cout<<ans<<endl;
    system("pause");
    return 0;
}

Magic Potion 2019南京

假设一个源点s连接每个英雄,再设一个汇点连接每个怪物之后去跑网络流得到答案ans,之后给每个英雄一瓶药水然后再跑一遍网络流得到答案ans1,然后答案就是ans+min(ans1,k);虽然是板子,但是还是没想出来呀,,,

2018南京区域赛-Problem I. Magic Potion_zxpzhangxinpeng的博客-CSDN博客

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define endl '\n'
#define lowbit(i) (i)&(-i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const ll mod=1e9+7;
const ll N=1000006,M=2000006;
const double inf=1e18;
const double eps=1e-8;
ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll getinv(ll a){return qpow(a,mod-2);}
ll lcm(ll a,ll b){
    return a*b/__gcd(a,b);
}
int n,m,k,s,t,ct;
int head[N],cnt=1,d[N],cur[N],vis[1005];
struct Edge{
    ll to,w,next;
}e[M];
void addedge(int from,int to,ll w){
    e[++cnt].to=to;
    e[cnt].w=w;
    e[cnt].next=head[from];
    head[from]=cnt;
}
bool bfs(){
    memset(d,0,(n+1)*sizeof(int));
    queue<int>q;
    q.push(s);d[s]=1;
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].next){
            int j=e[i].to;
            if(d[j]==0&&e[i].w){
                d[j]=d[u]+1;
                q.push(j);
                if(j==t) return 1;
            }
        }
    }
    return 0;
}
ll dfs(int u,ll mf){
    if(u==t) return mf;
    ll sum=0;
    for(int i=cur[u];i;i=e[i].next){
        int j=e[i].to;
        cur[u]=i;
        if(d[j]==d[u]+1&&e[i].w){
            ll f=dfs(j,min(mf,e[i].w));
            e[i].w-=f;
            e[i^1].w+=f;
            sum+=f;
            mf-=f;
            if(mf==0) break;
        }
    }
    if(sum==0) d[u]=0;
    return sum;
}
int dinic(){
    int flow=0;
    while(bfs()){
        memcpy(cur,head,sizeof head);
        flow+=dfs(s,1e18);
    }
    return flow;
}
int main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int a,b;
    cin>>a>>b>>k;
    n=a+b+2;
    s=a+b+1;t=a+b+2;
    for(int i=1;i<=a;i++){
        addedge(s,i,1);
        addedge(i,s,0);
    }
    for(int i=1;i<=a;i++){
        int tmp; cin>>tmp;
        for(int j=1;j<=tmp;j++){
            int u,v; cin>>v;
            u=i;v+=a;
            addedge(u,v,1);
            addedge(v,u,0);
            if(!vis[v]){
                vis[v]=1;
                // addedge(v,t,1);
                // addedge(t,v,0);
                ct++;
            }
        }
    }
    for(int i=1+a;i<=a+b;i++){
        addedge(i,t,1);
        addedge(t,i,0);
    }
    int ans=dinic();
    for(int i=head[s];i;i=e[i].next){
        e[i].w=1;
    }
    int ans1=dinic();
    cout<<ans+min(ans1,k)<<endl;
    system("pause");
    return 0;
}

G - Pyramid 数学推公式

先打一个表前几项是

1,5,15,35,70,126,210,330,495

进行第一次差分

1,4,10,20,35,56,84,120,165

第二次差分

1,3,6,10,15,21,28,36,45

第三次差分

1,2,3,4,5,6,7,8,9

最后可以发现这是一个等差数列,等差为1,那么通项公式an就是n的一个1次多项式,因为这是一阶等差数列,往上算去可以发现原式an是关于n的一个4次多项式,那么就可以根据拉格朗日插值带入5个点去算通项了;

也可以从第三次差分开始算起,第二次差分的每一项就是n(n+1)/2,那么第一次差分的每一项就是\sum_{i=1}^{n}\frac{i*(i+1)}{2},化简出来就是\frac{1}{12}(n*(n+1)(2*n+1)+3n(n+1)),之后原式也按这样的方式去求去化简最后就会得到\frac{1}{12}(2(\frac{n*(n+1)}{2})^{2}+n(n+1)(2n+1)+2n(n+1)),答案就出来了,化简中用到两个求和公式

1^{2}+2^{2}+3^{2}+...+n^{2}=\frac{n(n+1)(2n+1)}{6}

1^{3}+2^{3}+3^{3}+...+n^{3}=(\frac{n(n+1)}{2})^{2}   

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define endl '\n'
#define lowbit(i) (i)&(-i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const ll mod=1e9+7;
const ll N=1000006,M=2000006;
const double inf=1e18;
const double eps=1e-8;
ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll getinv(ll a){return qpow(a,mod-2);}
ll lcm(ll a,ll b){
    return a*b/__gcd(a,b);
}
ll t,n;
struct node{
    double x,y;
}a[1000006];
double dis(node a,node b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    cin>>t;
	while(t--){
		cin>>n;
		ll a=(n*(n+1)%mod),four=getinv(4LL);
		ll b=((2LL*a%mod)*a%mod)*four%mod,c=a*((2*n+1)%mod)%mod,d=2LL*a%mod;
		ll ans=(((b+c)%mod+d)%mod)*getinv(12LL)%mod;
		cout<<ans<<endl;
	}
    system("pause");
    return 0;
}