题挺好的,收获了许多
n是1--9,于是我们可以直接暴力,对于1注意特判开头0但N!=1,对于情报4,我们可以把a,b,c,d的所有取值枚举一遍,那么如何判断有无前导0?我们只要与10000...比即可,最后用2和3判断一下放入set中去重。
这里有一个小性质:判断是否可以被8除只要看后3位,因为前面的都乘了1000.
下面是AC代码:
- #include
- using namespace std;
- const int mod=1e9+7;
- int t,n,y;
- string s;
- void solve(){
- set<int>st;
- if(s[0]=='0'&&n!=1){
- cout<<0;
- return;
- }
- int mi=1;
- for(int i=2;i<=n;i++) mi*=10;
- if(n==1) mi=0;
- for(int a=0;a<=9;a++){
- for(int b=0;b<=9;b++){
- for(int c=0;c<=9;c++){
- for(int d=0;d<=9;d++){
- if(a==b||a==c||a==d||b==c||b==d||c==d) continue;
- for(int _=0;_<=9;_++){
- int x=0;
- for(int j=0;j
- if(s[j]<='9'&&s[j]>='0'){
- x=x*10+(s[j]-'0');
- }
- else{
- if(s[j]=='a'){
- x=x*10+a;
- }
- else if(s[j]=='b'){
- x=x*10+b;
- }
- else if(s[j]=='c'){
- x=x*10+c;
- }
- else if(s[j]=='d'){
- x=x*10+d;
- }
- else{
- x=x*10+_;
- }
- }
- }
- if(x>=mi&&x<=y&&x%8==0) st.insert(x);
- }
- }
- }
- }
- }
- cout<
size()%mod; - }
- int main(){
- ios::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- cin>>t;
- while(t--){
- cin>>n>>s>>y;
- solve();
- cout<
- }
- }
2.思维:
我们不妨把绝对值拆开,发现它就是两个点的min的两倍,那么对于任意两个点最小dis可能是这两个点较小的2倍,也可能是绕过最小点a[1]的4倍。
于是我们sort一下,从小到大枚举每一个点的贡献即可。
下面是AC代码:
- #include
- using namespace std;
- int n,t,a[200010];
- bool cmp(int a,int b){
- return a
- }
- void solve(){
- cin>>n;
- for(int i=1;i<=n;i++) scanf("%d",&a[i]);
- sort(a+1,a+n+1,cmp);
- long long sum=0;
- for(int i=1;i<=n;i++){
- sum+=4ll*min(2*a[1],a[i])*(n-i);
- }
- cout<
- }
- int main(){
- cin>>t;
- while(t--){
- solve();
- cout<
- }
- }
3.DP
直接按照题目要求DP会TLE,因此我们可以预先维护好每一张卡牌走1---n步的最小花费,同时注意到modn的性质,走n次一定会回到原点以此判断结尾。
dp[i][j]表示最大走i步后使聚合卡提高到j的最小代价,dp[0][0]=0,求dp[n][n-k],易得状态转移方程:
dp[i][j]=min(dp[i-1][j],dp[i-1][(j-i+n)%n]+min[i]),其中我们只用减一个i即可(因为走更多的话就不满足最大走i步的条件)
下面是AC代码:
- #include
- using namespace std;
- long long t,n,m,k,c[1110],a[1100],mins[5005],dp[5005];
- bool vis[5002];
- void solve(){
- for(int i=0;i<=n;i++) mins[i]=2e18;
- for(int i=0;i<=n;i++) dp[i]=2e18;
- for(int i=1;i<=m;i++){
- for(int j=1;;j++){
- if((a[i]*j)%n==a[i]%n&&j>1) break;
- int u=(a[i]*j)%n;
- mins[u]=min(mins[u],c[i]*j);
- }
- }
- dp[0]=0;
- for(int i=1;i<=n;i++){
- for(int j=0;j<=n;j++){
- dp[j%n]=min(dp[j%n],dp[(j-i+n)%n]+mins[i]);
- }
- }
- long long ww=dp[n-k];
- if(ww>=2e18) cout<<-1;
- else cout<
- return;
- }
- int main(){
- ios::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- cin>>t;
- while(t--){
- cin>>n>>m>>k;
- for(int i=1;i<=m;i++) cin>>a[i]>>c[i];
- solve();
- cout<
- }
- }
-
相关阅读:
CTF是黑客大赛?新手如何入门CTF?
Spring Security 自定义用户信息端点与多种登录方式共存
Kfka监控工具--Kafka-eagle安装
Unity IL2CPP 游戏分析入门
嵌入式复古游戏项目开发与实现
watchdog介绍
Java连接MySQL数据库
C/C++预定义宏、 #line 、#error、 #pragma和泛型选择
Js逆向教程20-Hook基础
ARouter出现 there‘s no route matched in group问题排查
-
原文地址:https://blog.csdn.net/cocoack/article/details/136852776