你最愿意做的哪件事，才是你的天赋所在

0%

发表于 Valine：

思路

根据题意可以发现答案肯定有一个在端点上，如果两个都不在端点上，那么可以通过平移得到相同的答案，所以最优的答案肯定有一个在端点上，考虑j在端点上。

阅读全文 »

发表于 更新于 Valine：

题目链接

LightOJ-1010
LightOJ-1008
LightOJ-1020

LightOJ-1008

思路

很多方法吧，我是观察到每轮的结束时1,4,9,25,36~~~,就是平方数，然后在判断它的偏移就好了。

代码实现

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
#include<bits/stdc++.h>
using namespace  std;
#define ll long long
int main(){
    int t;
    scanf("%d",&t);
    for(int cas = 1;cas<=t;cas++){
        ll x;
        scanf("%lld",&x);
        int pos = (int)sqrt(x);
        if(1ll*pos*pos!=x)pos++;
        int num = 2*pos-1;
        ll re = 1ll*pos*pos-x;
        printf("Case %d: ",cas);
        if(pos&1){
            if(re>num/2){
                printf("%d %d\n",pos,pos-(re-num/2));
            }else{
                printf("%d %d\n",1+re,pos);
            }
        }else{
            if(re>num/2){
                printf("%d %d\n",pos-(re-num/2),pos);
            }else{
                printf("%d %d\n",pos,1+re);
            }
        }
    }
}
阅读全文 »

发表于 更新于 Valine：

题目链接

Codeforces Round #641 (Div. 2)

A

思路

如果一个数的最小因子是2，那么加上2后肯定还是2，如果不是2，那么肯定是一个奇数，奇数+奇数=偶数，就会变成2，所以考虑第一次加的数，后面肯定都是2

代码实现
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<vll>
#define pii pair<int,int>
#define pll pair<ll>
inline bool isprime(ll num)
{if(num==2||num==3)return true;
    if(num%6!=1&&num%6!=5)return false;
    for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
    return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}
int main(){
   int t;
   scanf("%d",&t);
   while(t--){
       ll n,k;
       cin>>n>>k;
       ll ans = n;
       bool flag = 0;
       for(int i=2;1ll*i*i<=n;i++){
           if(n%i==0){
               flag = 1;
               ans+=i;
               break;
           }
       }
       if(!flag)ans+=n;
       ans+=(k-1)*2;
       cout<<ans<<endl;
   }
}
阅读全文 »

发表于 更新于 Valine：

题目链接

十七届同济大学程序设计预选赛-J

思路

我们从这个开始考虑

上面两个式子做差得到

阅读全文 »

发表于 Valine：

题目链接

gym-102392E

思路

首先按照年龄把这些人排好序。读题后发现答案为carpc+mpm+t*(需要变化的年龄),显然我们枚举车的数量后就可以知道m的大小，然后再求出最小的变化年龄就可以了。
处理四个数组

1
2
3
4
5
6
7
long long mned[N],msum[N],cned[N],csum[N];
/*
mned表示前i个全都乘坐单车需要多少变化的年龄
msum表示前i个全都乘坐单车多出多少年龄
cned表示前i个全部乘坐小车需要多少变化的年龄
csum表示前i个全部乘坐小车多出多少年龄
*/

阅读全文 »

发表于 Valine：

题目链接

NC17137

思路

DP状态定义为dp[i][j]表示前i个数删除j个后的答案。那么很容易得到递推方程

1
dp[i][j]=dp[i-1][j-1]+dp[i-1][j];

就是删除当前这个和不删除当前这个的情况，然后如果是 1 2 3 5 6 7 8 5 m=4的话，就会出现删除5 6 7 8 和删除6 7 8 5的情况重复的情况，我们需要减去重复的这部分，观察到重复的这部分需要把6 7 8给删除，就是把两个5之间的数全给删除了，于是重复的这部分就是dp[pos-1][j-(i-pos)]就代表中间的全部给删除了。

阅读全文 »

发表于 Valine：

题目链接

‘Educational Codeforces Round 86 [Rated for Div. 2]’

A

思路

水题，分三种情况就可以了

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define vi vector<int>
#define vll vector<vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
inline bool isprime(ll num)
{if(num==2||num==3)return true;
if(num%6!=1&&num%6!=5)return false;
for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int x,y;
		scanf("%d %d",&x,&y);
		int a,b;
		scanf("%d %d",&a,&b);
		ll ans = 1ll*(x+y)*a;
		if(x<y)swap(x,y);
		ans=min(ans,1ll*a*(x-y)+1ll*y*b);
		ans=min(ans,1ll*a*(x-y)+1ll*x*b);
		printf("%lld\n",ans);
	}
}
阅读全文 »

发表于 Valine：

题目链接

Gym-102392B

思路

对于每个任务要么选择level 1要么level 2或者不选，不选的话就会由上上个状态转移到，我们定义DP状态为dp[i][j]表示前n个物品中第一阶段经验为i，第二阶段经验为j的最小分钟数，需要给任务排序，因为会有溢出，防止出现{90,30,30,30}而应该选取{30,30,30,90}的情况。而第一阶段存在溢出的情况，所以只有在i < s1的时候进行转移。具体看代码实现

阅读全文 »