头像

追着你行走




离线:1个月前


最近来访(25)
用户头像
情断青丝
用户头像
MisakaMikoto
用户头像
少年补题王
用户头像
onepiece_8
用户头像
charlie_lzh
用户头像
码保过
用户头像
美帝解离开我的生活
用户头像
Wiselnn
用户头像
wugensheng
用户头像
带蓝子
用户头像
zqc
用户头像
肖肖_123
用户头像
Squtle
用户头像
rst
用户头像
卡塔利亚的骑士
用户头像
Rainiver
用户头像
wuwendongxi
用户头像
World_Devastator
用户头像
zwling
用户头像
404NotFound.

活动打卡代码 AcWing 1205. 买不到的数目

追着你行走
2021-04-14 23:46
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef long long ll;
typedef pair<int,int> pii;
bool dfs(int k,int i,int j) {
    if(!k) return 1;
    if(k>=i&&dfs(k-i,i,j)) return 1;
    if(k>=j&&dfs(k-j,i,j)) return 1;
    return 0;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    cout<<(n-1)*(m-1)-1; 

    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3254. Crontab

追着你行走
2021-04-10 18:52
#include<bits/stdc++.h>
using namespace std;
const int N=25;
int n;
unordered_map<string,int> mp;
void init() {
    mp["jan"]=1,mp["feb"]=2,mp["mar"]=3,mp["apr"]=4;
    mp["may"]=5,mp["jun"]=6,mp["jul"]=7,mp["aug"]=8,
    mp["sep"]=9,mp["oct"]=10,mp["nov"]=11,mp["dec"]=12;
    mp["sun"]=0,mp["mon"]=1,mp["tue"]=2,mp["wed"]=3,
    mp["thu"]=4,mp["fri"]=5,mp["sat"]=6;
}
struct Task{ //为-1表示可以用,0表示不可以用 
    bool mon[25],d[33],h[25],min[61],w[8];
    string name;
}task[N];
int months[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
struct Time{
    int year, month, day, hour, minute, week;
    Time(string str) {
        sscanf(str.data(), "%04d%02d%02d%02d%02d", &year, &month, &day, &hour, &minute);
    }
    bool operator< (const Time& t) const {
        if (year != t.year) return year < t.year;
        if (month != t.month) return month < t.month;
        if (day != t.day) return day < t.day;
        if (hour != t.hour) return hour < t.hour;
        return minute < t.minute;
    }
    int is_leap()   {
        return (year % 4 == 0 && year%100 || year%400 == 0);
    }
    int get_days() {
        if (month == 2) return months[2] + is_leap();
        return months[month];
    }
    void next() {
        if ( ++ minute == 60) {
            minute = 0;
            if ( ++ hour == 24) {
                hour = 0;
                week = (week + 1) % 7;
                if ( ++ day > get_days()) {
                    day = 1;
                    if ( ++ month > 12) {
                        month = 1;
                        year ++ ;
                    }
                }
            }
        }
    }
    bool check(Task& p) {
        return (p.mon[month]&&p.d[day]&&p.h[hour]&&
            p.min[minute]&&p.w[week]) ;
    }
    void print(Task& p) {
        printf("%04d%02d%02d%02d%02d ",year,month,day,hour,minute);
        cout<<p.name<<'\n';
    }
};
int get(string s) {
    if(isdigit(s[0])) return stoi(s);
    string str;
    for(auto it:s) str+=tolower(it);
    return mp[str];
}
void work(string s,bool a[],int len) {
    if(s=="*")
        for(int i=0;i<len;i++) a[i]=1;
    else {
        for(int i=0;i<s.size();i++) {
            int j=i+1;
            while(j<s.size()&&s[j]!=',') j++;
            string str=s.substr(i,j-i);
            i=j;
            int k=str.find('-');
            if(k!=-1) {
                int l=get(str.substr(0,k)),
                    r=get(str.substr(k+1)); 
                for(int k=l;k<=r;k++) a[k]=1;
            } else a[get(str)]=1;
        }
    }
}
int main(){
    init();
    string s,t;
    cin>>n>>s>>t;
    for(int i=1;i<=n;i++) {
        string min,h,d,m,w,name;
        cin>>min>>h>>d>>m>>w>>name; 
        work(min,task[i].min,60); //init
        work(h,task[i].h,24);
        work(d,task[i].d,32);
        work(m,task[i].mon,13);
        work(w,task[i].w,7);
        task[i].name=name;
    } 
    Time tt("197001010000"),st(s),en(t);
    tt.week=4; //保证week数据不需要求解 

    while(tt<en) {
        if(!(tt<st)) {
            for(int i=1;i<=n;i++) {
                if(tt.check(task[i] )) 
                    tt.print(task[i]);
            }
        }
        tt.next();
    }
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3260. 棋局评估

追着你行走
2021-04-09 17:17
#include<bits/stdc++.h>
using namespace std;
const int inf=1<<29;
static int c[4][4];
bool check(int x) {
    for(int i=1;i<=3;i++) {
        int a=0,b=0;
        for(int j=1;j<=3;j++) 
            a+=c[i][j]==x,b+=c[j][i]==x;
        if(a==3||b==3) return 1;
    }
    int a=0,b=0;
    for(int i=1;i<=3;i++) a+=c[i][i]==x,b+=c[i][4-i]==x;
    if(a==3||b==3) return 1;
    return 0;

}
int eval() {
    int res=0;
    for(int i=1;i<=3;i++) 
        for(int j=1;j<=3;j++) res+=c[i][j]==0;
    if(res==9) return 0;
    if(check(1)) return res+1;
    if(check(2)) return -res-1;
    if(res==0) return 0;
    return inf;
}
int dfs(int op) {
    int t=eval();
    if(t!=inf) return t;
    int res=op==1?-inf:inf;
    for(int i=1;i<=3;i++) {
        for(int j=1;j<=3;j++) {
            if(c[i][j]==0) {
                c[i][j]=op;
                if(op==1) res=max(res,dfs(3-op) );
                else res=min(res,dfs(3-op) );
                c[i][j]=0;
            }
        }
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    int t; cin>>t;
    while(t--) {
        memset(c,0,sizeof c);
        for(int i=1;i<=3;i++)   
            for(int j=1;j<=3;j++) 
                cin>>c[i][j];
        cout<<dfs(1)<<'\n';
    } 

    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3259. URL映射

追着你行走
2021-04-08 12:17
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
typedef long long ll;
typedef pair<int,int> pii;
struct node{
    vector<string> s;
    string name;
    int is; 
}dat[N];
vector<string> ans;
int n,m;
bool check(vector<string>& aa,vector<string>& bb,int a,int b) {
    ans.clear();
    int l=aa.size(),r=bb.size();
    for(int i=0;i<min(l,r);i++) {
        if(aa[i]==bb[i]) continue;
        else if(bb[i]=="<int>") {
            for(int j=0;j<aa[i].size();j++) 
                if(!isdigit(aa[i][j])) return 0;
            int j=0; //去除前导0 
            while(j<aa[i].size()-1&&aa[i][j]=='0') j++;
            ans.push_back(aa[i].substr(j) ) ;
        } 
        else if(bb[i]=="<str>") ans.push_back(aa[i]);
        else if(bb[i]=="<path>") {
            string t;
            for(int j=i;j<l;j++) {
                t+=aa[j];
                if(j<l-1) t+='/';
            }
            if(a) t+='/';//加入结尾符 
            ans.push_back(t);
            return 1;
        } 
        else return 0;
    }
    return l==r&&a==b;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int k=1;k<=n;k++) {
        string a,b; cin>>a>>b;
        dat[k].name=b;
        dat[k].is=a[a.size()-1]=='/'; //以什么结尾 
        string t;
        for(int i=1;i<a.size();i++) {
            t="";
            while(i<a.size()&&a[i]!='/') t+=a[i++];
            if(t.size()) dat[k].s.push_back(t);
        }
    }
    while(m--) {
        string a; cin>>a;
        vector<string> aa;
        int b=a[a.size()-1]=='/';
        string t;
        for(int i=1;i<a.size();i++) {
            t="";
            while(i<a.size()&&a[i]!='/') t+=a[i++];
            if(t.size()) aa.push_back(t);
        } 
        int flag=0;
        for(int i=1;i<=n;i++){
            if(check(aa,dat[i].s,b,dat[i].is) ) {
                cout<<dat[i].name<<' ';
                for(auto it:ans) cout<<it<<' ';
                flag=1;
                break;
            }
        }
        if(flag==0) cout<<404;
        cout<<'\n';
    }

    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3258. 碰撞的小球

追着你行走
2021-04-08 10:31
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef long long ll;
typedef pair<int,int> pii;
int a[N],dir[N],vis[N],n,t,l;

int main(){
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    cin>>n>>l>>t;
    for(int i=1;i<=n;i++) {
        cin>>a[i]; dir[i]=1;
    }
    for(int i=1;i<=t;i++) {
        memset(vis,0,sizeof vis);
        for(int j=1;j<=n;j++) {
            a[j]+=dir[j];
            if(vis[a[j]] ) dir[j]*=-1,dir[vis[a[j]] ]*=-1;
            else if(a[j]==0||a[j]==l) dir[j]*=-1;
            vis[a[j]]=j; //必为1 
        }
    }
    for(int i=1;i<=n;i++) cout<<a[i]<<' '; 
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3265. 再卖菜

追着你行走
2021-04-07 16:31
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
typedef long long ll;
typedef pair<int,int> pii;
int n,tot,head[N];
struct Edge{
    int v,next,w;
}edge[N*2];
void add(int u,int v,int w) {
    edge[++tot]={v,head[u],w};
    head[u]=tot;
}
int d[N],ins[N];
void spfa(int s) {
    memset(d,0xcf,sizeof d);
    queue<int> q;
    q.push(s); d[s]=0;
    ins[s]=1;
    while(q.size() ) {
        int x=q.front(); q.pop();
        ins[x]=0;
        for(int i=head[x];i!=-1;i=edge[i].next) {
            int v=edge[i].v,w=edge[i].w; //cout<<v<<'\n';
            if(d[v]<w+d[x]) {
                d[v]=w +d[x];
                if(ins[v]==0) ins[v]=1,q.push(v);
            }
        }
    } return ;
}
int a[N];
int main(){
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    cin>>n;
    memset(head,-1,sizeof head); 
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) {
        if(i==1) add(0,2,2*a[1]),add(2,0,-2*a[1]-1);
        else if(i==n) add(n-2,n,2*a[n]),add(n,n-2,-2*a[n]-1);
        else add(i-2,i+1,3*a[i]),add(i+1,i-2,-3*a[i]-2);
        add(i-1,i,1) ; //正整数 
    }
    spfa(0); //单源 最长路 
    for(int i=1;i<=n;i++) cout<<d[i]-d[i-1]<<' ';
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3264. 元素选择器

追着你行走
2021-04-07 11:02
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5,inf=1<<29;
int n,m;
struct node{
    int tab;
    string tag,id;
    int k; //
    node(string s) {
        int j=0;
        while(s[j]=='.') j++;
        tab=j/2;
        while(j<s.size()&&s[j]!=' ') tag+=tolower(s[j++]);
        j++;
        while(j<s.size()) id+=s[j++];
        k=0;
    }
    bool check(string s) {
        if(s[0]=='#') return s==id;
        return s==tag;
    }
    node(){ } //原始函数 
}d[N];
void solve(vector<string>& ws) {
    vector<int> res;
    stack<node> stk;
    for(int i=1;i<=n;i++) { //子序列 
        node t=d[i];
        while(stk.size()&&stk.top().tab>=t.tab) stk.pop();
        if(stk.size()) t.k=stk.top().k;
        if(t.k==ws.size() ) t.k--;
        if(t.check(ws[t.k])) {
            t.k++;
            if(t.k==ws.size()) res.push_back(i);
        }
        stk.push(t);
    }
    cout<<res.size()<<' ';
    for(auto it:res) cout<<it<<' ';
    cout<<'\n'; 
}
int main(){
    cin>>n>>m;
    getchar();
    for(int i=1;i<=n;i++) {
        string s; getline(cin,s);
        d[i]=node(s); //从0开始 
    } 
    for(int k=1;k<=m;k++) {
        string s; getline(cin,s);
        vector<string> t;
        stringstream ss(s);
        while(ss>>s) {
            if(s[0]!='#') for(auto& c:s) c=tolower(c);
            t.push_back(s); 
        }
        solve(t);
    }   
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3268. 小明放学

追着你行走
2021-04-05 21:46
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,inf=1<<29;
typedef long long ll;
int main(){
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    int tt[4];
    cin>>tt[1]>>tt[3]>>tt[2];
    ll s=tt[1]+tt[2]+tt[3];
    int n; cin>>n;
    ll ans=0;
    for(int i=1;i<=n;i++) {
        ll k,t; cin>>k>>t;
        if(k==2) k=3;
        else if(k==3) k=2;
        if(k==0)  ans+=t;
        else {
            ll res=ans%s;
            while(res>=t) {
                res-=t;
                if(k==3) k=1;
                else k++;
                t=tt[k]; //update
            }
            t-=res; //当前时间
            if(k==2) continue;
            else if(k==3) ans+=t+tt[1];
            else ans+=t; 
        }
    }
    cout<<ans<<endl;
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3270. 数据中心

追着你行走
2021-04-05 20:30
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,inf=1<<29;
typedef long long ll;
typedef pair<int,int> pii;
int n,m,r,tot=0,head[N];
struct Edge{
    int v,u,w;
    friend bool operator < (Edge a,Edge b) {
        return a.w<b.w;
    }
}edge[N];
void add(int u,int v,int w) {
    edge[++tot]={v,u,w};
}
int pre[N];
int get(int x) {
    if(x==pre[x]) return x;
    return pre[x]=get(pre[x]);
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    cin>>n>>m>>r;
    for(int i=1;i<=m;i++) {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w) ; //update
    }
    sort(edge+1,edge+1+m);
    for(int i=1;i<=n;i++) pre[i]=i;
    int ans=0;
    for(int i=1;i<=m;i++) {
        int u=edge[i].u,v=edge[i].v,w=edge[i].w;
        u=get(u),v=get(v);
        if(u==v) continue;
        else {
            pre[u]=v;
            ans=max(ans,w);
        }
    }
    cout<<ans<<'\n';
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3269. CIDR合并

追着你行走
2021-04-05 20:09
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5 ;
typedef long long ll;
struct node{
    ll val,len;
    friend bool operator < (node a,node b){
        if(a.val==b.val) return a.len<b.len;
        return a.val<b.val;
    }
}d[N];
bool subset(int a,int b) {
    ll la=32-d[a].len,lb=32-d[b].len;
    if(d[a].val+(1ll<<la)>=d[b].val+(1ll<<lb)&&d[a].val<=d[b].val) 
        return 1;
    return 0;
}
void print(node a) {
    ll x=a.val;
    for(int i=3;i>=0;i--) {
        cout<<x/(1ll<<i*8);
        x%=(1ll<<i*8) ;
        if(i==0) cout<<'/';
        else cout<<'.';
    }
    cout<<a.len<<'\n';
}
int n,tot;
bool check(int i,int k) {
    if(d[i].len==d[k].len) {
        ll rest=(1ll<<(33-d[i].len)) ; //剩余长度 
        if(d[i].val/rest==d[k].val/rest ) 
            return 1;   
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        string s; cin>>s;
        stringstream ss(s);
        int cnt=0,a=0;
        while(ss>>a) {
            cnt++;
            d[i].val=d[i].val*256+a;
            char ch;
            if(ss>>ch) {
                if(ch=='/'){
                    d[i].val*=1ll<<(32-8*cnt);//update val
                    ss>>a;
                    d[i].len=a;
                    break;
                } else continue;
            } else {
                d[i].val*=1ll<<(32-8*cnt);
                d[i].len=8*cnt;
                break;
            }
        }
    } sort(d+1,d+1+n);
    int k=1;
    for(int i=2;i<=n;i++) { //子集合并 
        if(!subset(k,i) ) d[++k]=d[i];
    }
    n=k; //init
    //cout<<k<<endl;
    k=1;
    for(int i=2;i<=n;i++){
        d[++k]=d[i];
        while(k>1&&check(k-1,k) ) {
            k-=2;
            d[++k].len-=1;
        }
    }
    //cout<<k<<endl;
    //print
    for(int i=1;i<=k;i++) print(d[i]);
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~