1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

/*
    vi
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cctype>
using namespace std;
const int maxkey=103;
const int maxl=2003;
char key[maxkey];int lenk;
char msg[maxl];int lenm;
char real[maxl];
void input()
{
    scanf("%s",key);
    scanf("%s",msg);
    lenk=strlen(key);
    lenm=strlen(msg);
}
char code(char c,int pos)
{
    int up,upk;
    if(isupper(c))up='A';
    else if(islower(c))up='a';
    
    if(isupper(key[pos]))upk=key[pos]-'A';
    else if(islower(key[pos]))upk=key[pos]-'a';
    
    return (c-up-upk+26)%26+up;
}
void solve()
{
    int kk=0;
    for(int i=0;i<lenm;++i)
    {
        real[i]=code(msg[i],kk);
        kk=(kk+1)%lenk;
    }
}
int main()
{
    //freopen("test3.in","r",stdin);
    input();
    solve();
    printf("%s\n",real);
    return 0;
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192

//NOIP 2012 Day1T2
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
template<typename T>
void read(T& w)
{
    char r;bool f=false;
    for(r=getchar();(r<48||r>57)&&r!='-';r=getchar());
    if(r=='-')r=getchar(),f=true;
    for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
    if(f)w=-w;
}
typedef long long lo;
const int maxn=100003;
const int maxm=100003;
int n,m,x0;
int near[maxn][3];
const int max2=17;

struct CITY
{
    int h,id;
    void init(int hh,int idd)
    {
        h=hh,id=idd;
    }
}city[maxn];
bool cmph(const CITY& a,const CITY& b)
{
    return a.h<b.h;
}

int to[maxn];
int pre[maxn],nxt[maxn];
void del(int k)
{
    int pree=pre[k],nxtt=nxt[k];
    nxt[pree]=nxtt;
    pre[nxtt]=pree;
}
CITY tmp[5];
int tk;
bool cmpd(const CITY& a,const CITY& b)
{
    int dda=abs(a.h),ddb=abs(b.h);
    if(dda!=ddb)return dda<ddb;
    else return a.h<b.h;
}
void initNear()
{
    sort(city+1,city+n+1,cmph);
    for(int i=1;i<=n;++i)
    {
        to[city[i].id]=i;
        
        pre[i]=i-1;
        nxt[i]=i+1;
    }
    for(int i=1;i<=n;++i)
    {
        int v=to[i];
        tk=0;
        for(int j=pre[v];j!=0&&j!=pre[pre[pre[v]]];j=pre[j])
            tmp[++tk].init(city[j].h-city[v].h,city[j].id);
        for(int j=nxt[v];j!=n+1&&j!=nxt[nxt[nxt[v]]];j=nxt[j])
            tmp[++tk].init(city[j].h-city[v].h,city[j].id);
        sort(tmp+1,tmp+tk+1,cmpd);
        if(tk>=1)
            near[i][1]=tmp[1].id;
        else near[i][1]=0;
        if(tk>=2)
            near[i][2]=tmp[2].id;
        else near[i][2]=0;
        del(v);
    }
}
int jump[maxn][max2+3];
lo da[maxn][max2+3],db[maxn][max2+3];
void initJump()
{
    for(int i=1;i<=n;++i)
    {
        int aim1=near[i][2];
        int aim2=near[aim1][1];
        jump[i][0]=aim2;
        da[i][0]=abs(city[to[aim1]].h-city[to[i]].h);
        db[i][0]=abs(city[to[aim2]].h-city[to[aim1]].h);
    }
    for(int k=1;k<=max2&&(1<<k)<=n;++k)
    {
        for(int i=1;i<=n;++i)
        {
            jump[i][k]=jump[jump[i][k-1]][k-1];
            da[i][k]=da[i][k-1]+da[jump[i][k-1]][k-1];
            db[i][k]=db[i][k-1]+db[jump[i][k-1]][k-1];
        }
    }
}
int going(int s,int limit,lo& suma,lo& sumb)
{
    int go=s;suma=0,sumb=0;
    for(int k=max2;k>=0;--k)
    {
        if(jump[go][k]&&suma+sumb+da[go][k]+db[go][k]<=limit)
        {		
            suma+=da[go][k];
            sumb+=db[go][k];
            go=jump[go][k];
        }
    }
    int aim=near[go][2];
    if(aim&&suma+sumb+abs(city[to[aim]].h-city[to[go]].h)<=limit)
    {
        suma+=abs(city[to[aim]].h-city[to[go]].h);
        go=aim;
    }
    return go;
}
void input()
{
    read(n);
    int hh;
    for(int i=1;i<=n;++i)
    {
        read(hh);
        city[i].init(hh,i);
    }
    read(x0);
    read(m);
}
int anss0=0;
lo ansa,ansb;

inline bool better(int s0,int sa,int sb)
{
    if(!anss0)return true;
    if(sa&&sb&&ansa&&ansb)
    {
        lo tans=lo(sa)*lo(ansb)-lo(sb)*lo(ansa);
        if(tans)return tans<0;
        else return city[to[s0]].h>city[to[anss0]].h;
    }
    if(sb==0&&ansb==0)
        return city[to[s0]].h>city[to[anss0]].h;
    else if(sb==0||ansb==0)
        return ansb==0;
    if(sa==0&&ansa==0)
        return city[to[s0]].h>city[to[anss0]].h;
    else if(sa==0||ansa==0)
        return sa==0;

}
void solve1()
{
    lo sa,sb;
    int tans;
    for(int i=1;i<=n;++i)
    {
        tans=going(i,x0,sa,sb);
        if(better(i,sa,sb))
            anss0=i,ansa=sa,ansb=sb;
    }
}

void solve2()
{
    int s,x;
    lo sa,sb;
    for(int i=1;i<=m;++i)
    {
        read(s),read(x);
        going(s,x,sa,sb);
        printf("%lld %lld\n",sa,sb);
    }
}
int main()
{
    //freopen("drive3.in","r",stdin);
    //freopen("drive.out","w",stdout);
    input();
    initNear();
    initJump();
    solve1();
    printf("%d\n",anss0);
    solve2();
    return 0;
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

/*
    king game
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
template<typename T>
void read(T& w)
{
    char r;
    for(r=getchar();r<48||r>57;r=getchar());
    for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
}
const int maxn=1003;
int n;
struct MAN
{
    int l,r;
    int pdt;
    inline void input(){read(l),read(r);pdt=l*r;}
}man[maxn];
bool operator<(const MAN& a,const MAN& b)
{
    return a.pdt<b.pdt;
}
void input()
{
    read(n);
    for(int i=0;i<=n;++i)
    {
        man[i].input();
    }
    sort(man+1,man+n+1);
}
struct num;
const int maxl=5003;
const int bit=100000000;
struct num
{
    int len;
    long long a[maxl];
    num(){len=1;memset(a,0,sizeof(a));}
    num(int w)
    {
        if(w==0)
        {
            a[1]=0;
            len=1;return;
        }
        len=0;
        while(w)
        {
            a[++len]=w%bit;
            w/=bit;
        }
    }
    num(long long w)
    {
        if(w==0)
        {
            a[1]=0;
            len=1;return;
        }
        len=0;
        while(w)
        {
            a[++len]=w%bit;
            w/=bit;
        }
    }
    void output()
    {
        if(len==1)printf("%d\n",a[1]);
        else
        {
            for(int i=len;i>=1;--i)
            {
                int tmpbit=bit/10;
                while(a[i]<tmpbit&&i!=len)
                {
                    putchar('0');
                    tmpbit/=10;
                }
                if(a[i])printf("%d",a[i]);
            }
            printf("\n");
        }
    }
};
num operator*(const num& a,const int& b)
{
    num ans;
    //if(b==0)return ans;
    ans.len=a.len;
    for(int i=1;i<=a.len;++i)
    {
        ans.a[i]+=b*a.a[i];
        if(ans.a[i]>=bit)
        {
            ans.a[i+1]+=ans.a[i]/bit;
            ans.a[i]%=bit;
            if(i+1>ans.len)ans.len=i+1;
        }
    }
    while(ans.a[ans.len]>=bit)
    {
        ans.a[ans.len+1]=ans.a[ans.len]/bit;
        ans.a[ans.len++]%=bit;
    }
    return ans;
}
num operator/(num a,const int& b)
{
    num ans;
    ans.len=0;
    for(int i=a.len;i>=1;--i)
    {
        if(a.a[i]>=b)
        {
            if(!ans.len)ans.len=i;
            ans.a[i]=a.a[i]/b;
            a.a[i]%=b;
        }
        a.a[i-1]+=a.a[i]*bit;
    }
    if(!ans.len)ans.len=1;
    return ans;
}
inline bool operator>(const num& a,const num& b)
{
    if(a.len!=b.len)return a.len>b.len;
    for(int i=a.len;i>=1;--i)
    {
        if(a.a[i]!=b.a[i])return a.a[i]>b.a[i];
    }
    return true;
}
void solveh()
{
    num sumh(man[0].l);
    num ans=0;
//	sumh=sumh*man[1].l;
    for(int i=1;i<=n;++i)
    {
        num tans=sumh/man[i].r;
        if(tans>ans)ans=tans;
        sumh=sumh*man[i].l;
    }
    ans.output();
}
int main()
{
    //freopen("test\\data\\game1.in","r",stdin);
    input();
    solveh();
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef long long LL;
void exgcd(LL a,LL b,LL& x,LL& y)
{
    if(b==0)
        x=1,y=0;
    else
    {
        exgcd(b,a%b,x,y);
    LL t=x;x=y,y=t-a/b*y;
    }
    
}
int main()
{
    LL a,b,x,y;
    scanf("%lld%lld",&a,&b);
    exgcd(a,b,x,y);
    printf("%lld\n",(x%b+b)%b);
    return 0;
}                        

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

/*
    lending classroom
    需要支持操作：区间减，区间最小值
*/
#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
inline void read(int& w)
{
    char r;
    for(r=getchar();r<47||r>57;r=getchar());
    for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
}
const int maxn=1000003;
const int maxm=maxn;
int n,m;
int rest[maxn];
int det[maxn];
void input()
{
    read(n),read(m);
    for(int i=1;i<=n;++i)
        read(rest[i]);
    for(int i=1;i<=n;++i)
    {
        det[i]=rest[i]-rest[i-1];
    }
}
struct Q
{
    int d,s,t;
}q[maxm];
int ans,id;
void solve()
{
    for(int i=1;i<=m;++i)
    {
        read(q[i].d),read(q[i].s),read(q[i].t);
            det[q[i].s]-=q[i].d;
            if(q[i].t<=n-1)det[q[i].t+1]+=q[i].d;
    }
    ans=m;
    int sum=0;
    for(int i=1;i<=n;++i)
    {
        sum+=det[i];
        while(sum<0)
        {
            if(q[ans].s>i)
                det[q[ans].s]+=q[ans].d;
            else if(q[ans].t>=i)
                sum+=q[ans].d;
            det[q[ans].t+1]-=q[ans].d;
            --ans;
        }
    }
}
int main()
{
//	freopen("classroom.in","r",stdin);
//	freopen("classroom.out","w",stdout);
    input();
    solve();
    if(ans==m)puts("0");
    else printf("-1\n%d\n",ans+1);
    return 0;
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218

//NOIP 2012 疫情控制
#include<iostream> 
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std;

template<typename T>
void read(T& w)
{
    char r;
    for(r=getchar();r<48||r>57;r=getchar());
    for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
}
const int maxn=50003;
const int maxm=50003;
int n,m;
typedef long long lo;
struct EDGE
{
    int to,nxt;
    lo w;
    void init(int too,int nxtt,lo ww)
    {
        to=too,nxt=nxtt,w=ww;
    }
}edge[maxn<<1];
int ek=0;

int node[maxn],head[maxn],d[maxn];
lo dis[maxn];
const int root=1;

int sk=0;
inline void addEdge(int from,int too,lo ww)
{
    edge[++ek].init(too,node[from],ww);
    node[from]=ek;
}
int army[maxm];
void input()
{
    read(n);
    int uu,vv;
    lo ww;
    for(int i=1;i<=n-1;++i)
    {
        read(uu),read(vv),read(ww);
        addEdge(uu,vv,ww);
        addEdge(vv,uu,ww);
    }
    read(m);
    for(int i=1;i<=m;++i)
    {
        read(army[i]);
    }
}
const int max2=16;
int up[maxn][max2+3];
void initUp()
{
    for(int k=1;k<=max2&&(1<<k)<=n;++k)
    {
        for(int i=1;i<=n;++i)
        {
            up[i][k]=up[up[i][k-1]][k-1];
        }
    }
}
int jump(int x,int t)//从k点向上跳，在t时间内最高能跳到哪 
{
    int go=x;
    for(int k=max2;k>=0;--k) 
    {
        if(up[go][k]&&dis[x]-dis[up[go][k]]<=t)		
            go=up[go][k];
    }
    return go;
}

int unable[maxm],uk=0;//不能到达根节点 
int able[maxm],ak=0;//能到达根节点

bool usedson[maxn];
int restson[maxn],rk=0;
bool ctrl[maxn];
void dfs(int k)
{
    int cnt=0;
    for(int i=node[k];i;i=edge[i].nxt)
    {
        ++cnt;
        int v=edge[i].to;
        if(d[v]>d[k]&&!ctrl[v])
        {
            dfs(v);
        }
    }
    if(cnt==1)
    {
        if(!usedson[head[k]])
        {
            restson[++rk]=head[k];
            usedson[head[k]]=true;
        }
    }
}
lo restt[maxn];
int minarmy[maxn];
bool cmp(const int& a,const int& b)
{
    return restt[a]>restt[b];
}
bool cmp2(const int& a,const int& b)
{
    return dis[a]>dis[b];
}
bool used[maxn];
bool can(int t)
{
    memset(used,0,(n+1)*sizeof(bool));
    ak=uk=rk=0;
    memset(usedson,0,(n+1)*sizeof(bool));
    memset(ctrl,0,(n+1)*sizeof(bool));
    memset(minarmy,0,(n+1)*sizeof(int));
    for(int i=1;i<=m;++i)
    {
        int v=army[i];
        if(dis[v]<=t)
        {
            able[++ak]=i;
            restt[i]=t-dis[v];
            if(restt[i]<restt[minarmy[head[v]]]||!minarmy[head[v]])
                minarmy[head[v]]=i;
        }
        else unable[++uk]=i;
    }

    for(int i=1;i<=uk;++i)
    {
        ctrl[jump(army[unable[i]],t)]=true;
    }

    dfs(root);
    if(rk>ak)return false;
    
    sort(able+1,able+ak+1,cmp);
    sort(restson+1,restson+rk+1,cmp2);
    for(int i=1,j=1;i<=rk;++i)
    {
        while(used[able[j]]&&j<=ak)
            ++j;
        if(j<=ak)
        {
            if(minarmy[restson[i]]&&!used[minarmy[restson[i]]])
                used[minarmy[restson[i]]]=true;
            else if(restt[able[j]]>=dis[restson[i]])
                used[able[j]]=true,++j;
            else return false;
        }
        else return false;
    }
    return true;
}
int ans=-1;
void BS()
{
    int l=1,r=int(1e9),mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(can(mid))
        {
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
    }
}

void build(int k)
{
    for(int i=node[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(!d[v])
        {
            d[v]=d[k]+1;
            up[v][0]=k;
            if(k==root)
                head[v]=v,++sk;
            else head[v]=head[k];
            dis[v]=dis[k]+edge[i].w;
            build(v);
        }
    }
}

void solve()
{
    d[root]=1;
    dis[root]=0;
    build(root);
    initUp();
    if(m>=sk)
        BS();
}
int main()
{
    //freopen("blockade9.in","r",stdin);
    //freopen("blockade.out","w",stdout);
    input();
    solve();
    printf("%d\n",ans);
    return 0;
}