`
hellojyj
  • 浏览: 61472 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

UVA 10036 Divisibility

    博客分类:
  • ACM
 
阅读更多

原题传送门:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=977

 

 

Consider an arbitrary sequence of integers. One can place + or - operators between integers in the sequence, thus deriving different arithmetical expressions that evaluate to different values. Let us, for example, take the sequence: 17, 5, -21, 15. There are eight possible expressions:

 

17 + 5 + -21 + 15 = 16
17 + 5 + -21 - 15 = -14
17 + 5 - -21 + 15 = 58
17 + 5 - -21 - 15 = 28
17 - 5 + -21 + 15 = 6
17 - 5 + -21 - 15 = -24
17 - 5 - -21 + 15 = 48
17 - 5 - -21 - 15 = 18

 

We call the sequence of integers divisible by K if + or - operators can be placed between integers in the sequence in such way that resulting value is divisible by K. In the above example, the sequence is divisible by 7 (17+5+-21-15=-14) but is not divisible by 5.

 

You are to write a program that will determine divisibility of sequence of integers.

 

Input

 

The first line of the input file contains a integer M indicating the number of cases to be analyzed. Then M couples of lines follow. 
For each one of this couples, the first line contains two integers, N and K (1 <= N <= 10000, 2 <= K <= 100) separated by a space. The second line contains a sequence of N integers separated by spaces. Each integer is not greater than 10000 by it's absolute value.

 

Output

 

For each case in the input file, write to the output file the word "Divisible" if given sequence of integers is divisible by K or "Not divisible" if it's not.

 

Sample input

 

2
4 7
17 5 -21 15
4 5
17 5 -21 15

 

Sample Output

 

Divisible
Not divisible

分析:
DP

 

•f[i][j]=1表示前i个数字形成的表达式的值除以K之后可以余j

 

•f[0][0]=1

 

•考虑第i个数字x,假设它是正的。

 

•如果 f[i-1][j] = 1,说明前i-1个数字的表达式的值除以K可以余j

 

•在x的前面放“+”, f[i][(j+x)%K] = 1

 

•在x的前面放“-”,f[i][(j-x+K)%K]=1
 
#include<cstdio>
#include<cstring>
int t,n,k,num,cur;
bool dp[2][100];
int main(){
    scanf("%d",&t);
    while(t--){
        cur = 0;
        memset(dp,false,sizeof(dp));
        dp[0][0] = true;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++){
            cur ^= 1;
            memset(dp[cur],false,sizeof(dp[cur]));
            scanf("%d",&num);
            if(i>1 && num<0)
                num = -num;
            num %= k;
            for(int j=0;j<k;j++){
                if(dp[cur^1][j]){
                    dp[cur][(j+num+k)%k] = true;
                    if(i>1)dp[cur][(j-num+k)%k] = true;
                }
            }
        }
        printf("%s\n",dp[cur][0]?"Divisible":"Not divisible");
    }

    return 0;
}
 
分享到:
评论

相关推荐

    VIsibility属性

    VISIBILITY属性详解 在 Android 开发中,控件的可见性是非常重要的,VISIBILITY 属性就是控制控件的显示和隐藏的。通过设置 VISIBILITY 属性,我们可以控制控件的可见性,达到不同的显示效果。 VISIBLE、INVISIBLE...

    WPF的bool2Visibility转换器使用

    `BoolToVisibilityConverter` 是一个内置的数据转换器,它用于将布尔值(`bool`)转换为 `Visibility`枚举类型,这对于根据逻辑状态控制UI元素的可见性非常有用。在本教程中,我们将深入探讨如何使用`...

    Android中visibility属性

    在Android开发中,`visibility`属性是控制UI组件可见性的重要元素,广泛应用于各种视图控件,如TextView、ImageView、Button等。该属性决定了一个控件是否在屏幕上显示,以及如何显示。`visibility`属性有三个可能的...

    display与visibility的区别

    ### Display与Visibility的区别 在网页布局与样式设计中,`display`与`visibility`属性是控制元素显示状态的两种常用方式。尽管它们都能达到隐藏或显示元素的目的,但两者之间存在本质的区别。本文将深入探讨这两种...

    前端项目-visibility.js.zip

    《前端项目中的Page Visibility API与visibility.js库》 在当今的Web开发中,前端性能优化是不可或缺的一部分。其中,理解用户与页面的交互状态对于提升用户体验至关重要。这就是Page Visibility API和`visibility....

    DataGrid_Column_Visibility_Binding

    return (value is Visibility visibility) && visibility == Visibility.Visible; } } ``` 接下来,你需要在你的XAML资源字典中声明这个转换器: ```xml ``` 这里的`local`是命名空间前缀,需要根据实际...

    JS中style.display和style.visibility的区别实例说明.docx

    JS 中 style.display 和 style.visibility 的区别实例说明 在 JavaScript 中,style.display 和 style.visibility 是两种常用的控制元素显隐的方法,但是它们之间有着根本的区别。 style.display style.display ...

    对比: display, visibility(有代码)

    在网页设计和开发中,`display` 和 `visibility` 是两个非常重要的CSS属性,它们用于控制元素在页面上的可见性和布局。这篇博客文章通过代码示例深入探讨了这两个属性的区别和用法。 首先,`display` 属性主要用于...

    Modeling Mutual Visibility Relationship in Pedestrian Detection

    Modeling Mutual Visibility Relationship in Pedestrian Detection Modeling Mutual Visibility Relationship in Pedestrian Detection Modeling Mutual Visibility Relationship in Pedestrian Detection

    CSS隐藏元素 display visibility opacity的区别.docx

    在CSS中,隐藏元素的方法主要有三种:`display:none`、`visibility:hidden`和`opacity:0`,它们各自有不同的特点和适用场景。 1. `display:none`:此属性会使元素完全从页面布局中消失,不占据任何空间。元素及其...

    satellite visibility_satellite_卫星轨道计算

    "satellite visibility_satellite_卫星轨道计算"这个标题暗示我们要讨论的是如何预测和计算卫星在特定地点的可见性,这对于地面站接收信号或者规划卫星任务来说是极其关键的。 首先,卫星的轨道是由它的六根数(也...

    Flutter Offstage、Visibility隐藏/可见

    Flutter Offstage、Visibility隐藏/可见。

    virtual_visibility

    标题“virtual_visibility”和描述“virtual netflow visibility,my test”提及的核心概念是虚拟网络的NetFlow可视性。NetFlow是一种由Cisco系统开发的技术,用于收集、分析和记录网络流量数据,以帮助网络管理员...

    flutter_keyboard_visibility

    keyboard_visibility 通知服务,用于软键盘可见性 用法 将依赖项添加到项目的根文件夹中的pubspec.yaml文件中。 查找“ dependencies:”行,并在此行之后添加以下行: keyboard_visibility: any 或者 keyboard_...

    visibility_2020建模_2020数学建模_参数估计_数学建模_Visibility_

    在数学建模领域,"visibility_2020建模_2020数学建模_参数估计_数学建模_Visibility_"这个标题暗示了我们正在探讨2020年数学建模竞赛中的一项任务,特别关注的是“Visibility”问题,这可能涉及对某个系统或现象的...

    使用 content-visibility 优化渲染性能.doc

    【content-visibility】属性是CSS中的一个新特性,它允许开发者控制元素是否渲染其内容,以及何时渲染。这个属性能够显著提升网页的初始加载速度,因为它让浏览器可以在内容需要显示之前跳过大量的布局和渲染工作。 ...

    浅析Android中的visibility属性

    在Android开发中,`visibility`属性是控制UI组件(如按钮、文本视图等)是否在屏幕上显示的关键属性。它提供了三个可能的值,每个值都有特定的效果: 1. **可见(Visible)**:当`visibility`设置为`visible`时,...

    CSS:Visibility 和 Display 属性的比较.pdf

    `visibility`属性有四个可选值:`visible`(默认值,元素可见)、`hidden`(元素不可见但保留空间)、`collapse`(仅对表格元素有效,移除元素但不影响布局)和`inherit`(继承父元素的`visibility`值)。...

    display和visibility的区别示例介绍

    在网页布局和样式设计中,`display` 和 `visibility` 是两个非常重要的CSS属性,它们都能用来控制元素的可见性,但实现方式和效果大不相同。本篇文章将深入探讨两者之间的区别,并通过示例来具体说明。 首先,`...

Global site tag (gtag.js) - Google Analytics